Multifidelity Reinforcement Learning with Control Variates
Authors: Sami Khairy
Prasanna Balaprakash
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Reinforcement learning
multifidelity environments
multifidelity estimation

Abstract: In many computational science and engineering applications, the output of a system of interest corresponding to a given input can be queried at different levels of fidelity with different costs. Typically, low-fidelity data is cheap and abundant, while high-fidelity data is expensive and scarce. In this work we study the reinforcement learning (RL) problem in the presence of multiple environments with different levels of fidelity for a given control task. We focus on improving the RL agent's performance with multifidelity data. Specifically, a multifidelity estimator that exploits the cross-correlations between the low- and high-fidelity returns is proposed to reduce the variance in the estimation of the state-action value function. The proposed estimator, which is based on the method of control variates, is used to design a multifidelity Monte Carlo RL (MFMCRL) algorithm that improves the learning of the agent in the high-fidelity environment. The impacts of variance reduction on policy evaluation and policy improvement are theoretically analyzed by using probability bounds. Our theoretical analysis and numerical experiments demonstrate that for a finite budget of high-fidelity data samples, our proposed MFMCRL agent attains  superior performance compared with that of a standard RL agent that uses only  the high-fidelity environment data for learning the optimal policy.

Multifidelity Reinforcement Learning with Control Variates
Anonymous Author(s)
Affiliation
Address email
Abstract
In many computational science and engineering applications, the output of a system of interest corresponding to a given input can be queried at different levels of fidelity with different costs. Typically, low-fidelity data is cheap and abundant, while high-fidelity data is expensive and scarce. In this work we study the reinforcement learning (RL) problem in the presence of multiple environments with different levels fidelity for given control task. We focus on improving the RL agent's performance with multifidelity data. Specifically, a multifidelity estimator that exploits the cross-correlations between the low- and high-fidelity returns is proposed to reduce the variance in the estimation of the state-action value function. The proposed estimator, which based on the method control variates, is used to design multifidelity Monte Carlo RL (MFMCRL) algorithm that improves the learning of the agent in the high-fidelity environment. The impacts variance reduction analyzed by using probability bounds. Our theoretical analysis and numerical experiments demonstrate that for finite budget of high-fidelity data samples, our proposed MFMCRL agent attains superior performance compared with that of a standard RL agent that uses only the high-fidelity environment data for learning the optimal policy.
2
6
10
12
policy evaluation and policy improvement are theoretically
14
15
18
17
18
Introduction
20 Within the computational science and engineering (CSE) community, multifidelity data refers to 21 data that comes from different sources with different levels of fidelity. The criteria by which data is considered to low fidelity or high fidelity vary across different applications, but usually low-fidelity data is much cheaper to generate than high-fidelity data under some cost metric. In robotics for
22
24 instance, data coming from robot operating in the real world constitutes high-fidelity data, while simulated data of the robot based on first principles is considered to be fow-fidelity data. Different simulators of the robot can also be designed by increasing the modeling complexity. A simulator that takes into account aerodynamic drag is, for instance, of higher fidelity than one that is based only on the simple laws of motion. As another example, a neural classifier in deep learning can be trained the full training data for large number of training epochs,
26
28
subser of the training 30 data for few epochs. Evaluating the trained model on a held-out validation data set in the former
31 case yields a higher-fidelity estimate of the classifiers' performance compared with that in the latter
32 case. In general, low-fidelity data serves as an approximation to its high-fidelity counterpart and
33 can be generated cheaply and abundantly (24). Many outer-loop applications that require querying
34 the system at many different inputs, including black-box optimization (21]. inference [29], and
35 uncertainty propagation 19 27. can exploit the cross-correlations between low- and high-fidelity
36 data to solve new problems that would otherwise be prohibitively costly to solve using high-fidelity
37
data alone 28 29
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

38
Motivated by the advent of multifidelity data sources within CSE, in this work we study the rein- forcement learning (RL) problem in the presence of multiple environments with different levels of fidelity for given control task. RI. is a popular machine learning paradigm for intelligent sequential decision-making under uncertainty, enabling data-driven control of complex systems with scales ranging from quantum [8] to cosmological [26]. State-of-tthe-ar model-free RI algorithms have indeed demonstrated sheer success for learning complex policies from raw data in singlc-fidelity environments [25 22
39
40
41
42
43
44
32 [2). This success, however, comes at the cost of requiring large num- ber of data samples to solve a control task satisfactorily) In the presence of multiple environments with different levels of fidelity, new ways arise that could help the agent learn better policies. One way that has been well studied in the context of RL is transfer learning (TL). In TL [3, g 39 the agent first uses the low-fidelity environment to learn a policy that is then transferred (directly or
31
45
47
49 indirectly through the transfer of the state-action value function) to the high-fidelity environment
50
as heuristic bootstrap learning. Essentially, TL. attempts leverage multifidelity environments dilemma that is present within RL, and it works under the assumption that the maximum deviation between the optimal low-fidelity state-action value function and the optimal high-fidelity state-action value function is bounded with a threshold that is used
51 to deal with the exploration-exploine
52
59
54 by TL for bootsrapping the high-fidelity value function [9] In our work we explore an uncharted
55 territory and focus on multifidelty estimation in RL and its role in improving the learning of the
56 agent. We demonstrate that as long as the low- and high-fidelity state-action value functions for any policy are correlated, significant performance improvements can be reaped by leveraging these process.
57
58
correlaorsss without extra effort in managing the
59
The main contributions of our work are summarized as follows. First, we study generic multifidelity setup in which the RL agent can execute a policy in two environments, low-fidelity environment and a high-fidelity environment. To leverage the cross-correlations between the low- and high-fidelity returns, we propose an unbiased reduced-variaacc multifidelity estimator for the state-action value function based on the framework of control variates. Second, a multifidelity Monte Carlo (MC) RL algorithm, named MFMCRL, is proposed to improve the learning of the RL agent in the high-fidelity environment. For any finite budget of fighlfideiity environment interactions, MFMCRL leverages low-fidelity data to learn better policies than a standard RL agent that uses only the high-fidelity data. Third, we theoretically analyze the impacts of variance reduction in the estimation of the state- action value function on policy evaluation and policy improvement using probability bounds. Fourth, performance gains of the proposed MFMCRL algorithm are empirically assessed through numerical experiments synthetic multifidelity environments, as well as a neural architecture search (NAS) use case.
60
61
62
63
64
65
66
87
68
69
70
71
2
Preliminaries and related work
72
73
2.1
Reinforcement learning
74. We consider episodic RL problems where the environment Σ is specified by an infinite-horizon
75 Markov decision process (MDP) with discounted returns [5) Specifically, an infinite-horizon MDP
76 is defined as a tuple M = (S, A, P, 3, R,y), 7), where S and A are finite sets of states and actions,
77 respectively; P S x A S + [0, 1] the environment dynamics; and B S + [0, 1] is the
78 initial distribution over the states, that is, 8(s) = Pr = s), Vss E S. The reward function R is bounded and defined as S x A [Rmin: Bmax]. where Rmin and Rmax are real numbers. y a
79
80 discount factor to bound the cumulative rewards and trade off how far- or short-sighted the agent is
81 in its decision making. The environment dynamics, P(s'|s. (ss a). Vs, a, s' E x A S, encode the stationary transition probability from a state to a state s' given that action a is chosen [6]. In the episodic setting, there exists at least one terminal state 8T such that P(s'|s7 a) = 0, Va, s' f ST and P( (st, a)- 1, Va, i.e. 8T is an absorbing state. Furthermore, B(8T) = 0 and R(ST, a) 0, Va.
82
85
84
85 When the RL agent transitions into a terminal state, all subsequent rewards are zero, and simulation
86 is restarted from another state ~ B.
87 The agent's 's decision- process is characterized by π (als), which a Markov stationary policy
88 that defines a distribution over the actions a E A given a state s E S. In the RL problem, P
Poor sample complexity of model-free RL algorithms has long motivated developments in model-based RL, where a predictive model of the environment is learned alongside the policy [14] 30). Our work is focused on model-free RL.
2

---

and R are not known to the agent, yet the agent can interact with the environment sequentially 89
90 discrete time steps, t = 2. T, by exchanging actions and rewards. Notice that is random variable and denotes the time step at which the agent transitions into terminal state. At
91
92 each time step the agent observes the environment's state & = 8 E S, takes action at a ~ 93 (als) A, and receives a reward r++1 R(s,aa a). The environment's s state then evolves to new state St+1 = s' P(s"|s, a). The state-value function of state s under a policy π is defined as the expected long-term discounted returns starting in state and following policy thereafter,
94
7 at) = o] In addition, the state-action value function of a 96 V (8) = E Eacoaa
state 8 and action a under a policy æ is defined as Qn a) -a \ R'(s (s) 87
98
40 a
that Notice that (s) = Ea-s [Q (s, a)]. The solution of the RL problem is policy n
99
maximizes the discounted returns from the initial state distribution '² = argmax E (s)). is
well known that there exists at least one optimal policy x² such that Vg. (s) max VG (s) e and Q (s, a) max Qn Vs, a 8 A [2]. Furthermore, a deterministic policy that selects 101
100
x
102
the greedy action with respect to Qx (s, a), Vs S, an optimal policy.
103
2.2
Control variates
104
The method of control variates is variance reduction technique that leverages the correlation between random variables (r.vs.) to reduce the variance an estimator (20]. Let W1, W2. ... W
105
Mw.. and IIWW Mw ]²] = o² w Vi E [n]. In addition, let Z1, -., Zn, be n i.id. r.v. such that E[Z,] = Mzz and
be independent and identically distributed (i.i.d) L.s. such that [[[;]]
107
108
ZZ 22 ) = o Vi E [n]. Suppose that W,, Zj are correlated with a correlation coefficient
Covl Z. W.) Vi [n). where Cov Z,, W.] B[Z.W;] [[Z is the covariance Pw.z Voz Vo
109
110
between Z, and W, Furthermore, suppose that W,, Zj are independent and thus uncorrelated Vi * Using the Cauchy- Schwartz inequality, one show that |Pw.z S 1.
112 To estimate ww- we first consider the sample mean estimator, 0, 1 n Σ W,. 01 is an unbiased estimator of Mw in other words, [[0:] Σ;= E[W.] Mw and has variance Varlo 114
o
Next, we consider the control-varian variate---bebbbae based estimator.
02 = 1 Σ
W + alZi M2))
02 is also unbiased estimator of Mw,, i.c., [[02] = Mw yet it has variance Var[0g] 1 Var(W, DaCoolZZ, W.l). The variance of 02 can be controlled and 117 minimized by setting a to the minima of Var + a Var [Z,] + 22Covv Wi]. which is attained Hence, by introducing a<?, 12)) as control variate, the
116 a( Z2 (1 ) = 1 [V,
" [.WW]++dl aar
118 at ax Cov(Z,.
Sw.
Pz.w oz
variance of 0g is reduced,
119
Var = -1 P2 Z. Var[O1].
(2)
Because 0g is an unbiased estimator, 02 has lower mean squared error (MSE) by the bias-variance decomposition theorem of the MSE. Applications of the method of control variates extend beyond
120
121
122
variance reduction. For example, the concept of control variates used in (27] design fusion framework to combine an arbitrary number of surrogate models optimally.
123
124
2.3
Related work
In M1 a policy search algorithm proposed that leverages a crude approximate model P. of the true 125
MDP to quickly learn to perform well on real systems. The proposed algorithm, however, is limited 127 to the case where P is deterministic, and assumes that model derivatives are good approximations of the true derivatives such that policy gradients can be computed by using the approximate model.
3

---

129
In transfer learning (TL) [3 23], value, model, or policy parameters are transferred in one direction as a heuristic initialization to bootstrap learning in the high-fidelity environment, with no option for backtracking. The option for the agent to backtrack and to choose which environment to use is studied in the multifidelity RL (MFRL) work of [9. That algorithm extended in [3 by integrating function approximation using Gaussian processes 18 As in TI., both [9] and 33 use the value function from fower-fidelity environment as a heuristic to bootstrap learning and guide exploration in the high-fidelity environment. From an optimization viewpoint, this approach is reasonable only the lower- fidelity value function lies in the vicinity of the optimal high-fidelity value function, a situation that cannot be guaranteed or known priori in general. Hence, in ( 33 it is assumed that the optimal state-action value function in the low- and high-fidelity, environments differ by no more than small parameter B at every state-action pair, and they require the knowledge of B priori to across multifidelity environments. By contrast, we require only that the low- and high-fidelity returns are correlated in our work, and the correlation need not be known a priori. The correlcorrel between the low- and high-fidelity returns is used for reducing the variance in the estimation of the high-fidelity state-action value function, and hence our approach is complementary to existing TL techniques that use multifidelity environments for guided exploration We show that as long as the low- and high-fidelity state-action value function of policy are correlated, the agent can benefit from the cheap and abundantly available low-fidelity data to improve its performance, without altering the exploration process.
130
132
133
134
136
138
manage sxplorationexpplotaaiee
140
142
143
144
145
33).
146
147
3
Multifidelity estimation in RL
148
149
3.1
Problem setup
We consider a multifideeity setup in which the RL agent has access to two environments, Ele and I
150
modeled by the two MDPs M = (Sle .A. , Rlo 7), and M = (Shi. .A, phi, , Rhi 7).
151
respectively, shown in Figure I Ed is fow-fidelity environment in which the low- fow-fidelity reward function R S x A
152
+ Rlo min: Rlnnn and the low-fidelity dynamics pla are chear 2 to evaluate/simulate, yet they are potentially inaccurate. On the other hand, Ii is a high-fidelity enviromment in which the high-fidelit reward function Rhi S x A + [ Rii and the high- fidelity dynamics phi describe the real-world system with the highest accuracy, yet they are expensive to evaluate/simulate []. We stress that (Phi, ghi Rh)) and (plo, Rlo) are unknown to the agent, and interaction with the two environments is only through the exchange of states, actions, next states and rewards, which is the typical case in RL.
153
154
155
156
157
158
160
The action space A is the same in both environments, yet the state space may differ. It is assumed that the low-fidelity state space is a subset of the high-fidelity state space, S C 8hi in other words, the states available the low-fidelity environment are a subset of those available at the sigeiiielitty environment, and it is assumed that there exists a known mapping T Shi + S as in previous works 36 High- High-fidelity environments usually capture more state information than do low- fidelity environments so T can be many-to-on map. Access to the high-fidelite simulator Dd is restricted to full episodes ببر = =(bbi (g, r-h gli
161
162
163
164
165
186
81 a1, r2 ,
) On the other hand, Ele is generative, and
simulation can be started by the agent at any state-action pair [7. 17. Using T and Σ the agent T (shi)). and it is assumed that Pr((" > 0 under plo and : It is also assumed that R (T(s")) a) and Rhi(s" a) are correlated.
167
can map hi to r (T(sf)), ), 0o, rl. T(s)), 01 r/., (s
168
170
Based on this setup, a correlation exits between the low- and high- fidelity trajectories that can be beneficial for policy learning. In this work we study how to leverage the cheaply accessible low-fidelity trajectories from Elo to learn an optimal x² that maximizes
171
172
173
in other words, to learn x² that is optimal with respect to the high-fidelity environment Ehi
gh
Ee (s" ss)
174
Sampling cost is application dependent. is up the practitioner to assign cost and determine low- and high-fidelity sampling budgets.
'T is problem-specitic. For instance, if shi represents fine grid and She represents a coarse grid, then T will map " to the closest 5 based chosen distance metric.

---

175
3.2
Multifidelity Monte Carlo RL
1 R
hi R
178
The Monte Carlo method to solve the RL prob- lem is based on the idea of averaging sample returns. In the MC method, experience is di- vided into episodes. At the end of an episode, state-action values are estimated, and the policy is updated. For ease of exposition, we consider specific state-action pair (s"i, a) in what follows and suppress the dependence on (s"), a) from the notation to avoid clutter. Consider a sam- ple trajectory y that results from the agent's interaction with the high-fidelity environment starting at (shi shi ag a) and following т, that is, 7 : a0.77... s ,1,01, a1, rhi S7.
t s
8 Sth
177
Low-fidelity environment E
High fidelity environment E
178
179
a A
RL agent
6 A
180
182
Figure 1: RL with low- and high-fidelity environ- ments. Σ cheap to evaluate but potentially inaccurate. Σdh represents the real world with the highest accuracy, yet it is expensive to evaluate.
184
186
The RL agent leverages the correlations between the low- and high-fidelity data to learn Thi
188
Note that phi = (s"", ac). Let G denote the corresponding long-term discounted return, ghi -i 7 The high-fidelity state-action value of the pair (s, a) when the agent follows π
189
190
(* aa) = E,, [g = s 0g = a]-
(3)
Notice that Q a) is the expectation of an r.v. ghi with respect to the random trajectory yبر ghi
192
13th flma] and has a finite variance given by is a bounded r.v. with support on the interval 11-y" I-y.
193
i (s .) = E,," ( - Q .a)) s.h 00 = a)
(4)
194
By interacting with the environment, the agent can sample only a finite number of trajectories, n.
Let The thi ti be the n sampled trajectories that starts at the pair (s"i a). Furthermore, let
195
198
GT G
Ghi be i.i.d. r.v.. that correspond to the long-term discounted returns of the sampled E, [
197
trajectories, 7h" , .Ta respectively. Notice that E,t [ (s, The virst MC sample average is
E, 1
198
Qni nnn (s a)
1 Σ ghi
(5)
By the weak law of large numbers, lim Pr( m (s a) @ (6' a)) > E) = 0, for any positive number &. In addition, the variance of this unbiased sample average estimator is
199
200
Var Qu (s ai) (s";
(6)
n
201
Using the low-fidelity generative environment and the method of control variates, we design an unbiased estimator for the expected long-term discounted returns that has a smaller variance than 6). Let 7."" be the ith low-fidelity trajectory that is obtained from Th by using T and the generative low- fideeielytty environment to evaluate r.oo = (T a.). Let g be the r.v. which corresponds to
203
204
the long-term discounted return of 7/00 Notice that 9hi and Glo are correlated r.v. this multifidelity setup. Based on those low- wow-fidelity trajectories, the low-fidelity first-visit MC sample average is n (T(s"), a) = = Ei= G/00 and has a variance of Var Q o (T.... a) = ( where of ).)) a) E,, (g QT a)) 9Isu T((hi) au = and Q a) is the true 208
205
207
209
population mean.
210
Using the method of control variates presented in Subsection 2.2 we propose the following multifi- delity MC estimator:
211
(S (s"i.a) a) =Q (s",,)) a) + añ ( - ( a)). F.n
212
where
Cov [Qhi (sMi a), Q10 (s)
(8)
Var Q
F. (ssh)),a))
5

---

213
Notice that the estimator in 7 is unbiased and has variance of
Var @ (s a)] -1- Var @ (s .0)
(9)
long-term dis- where Ps.a is the correlation coefficient between the low-fidelity and counted returns:
215
Cov [Qth (s"). a), Q% (T(s")),
Ps.a
(10)
Var ( an) Var @ (T (s)
216
Therefore, the variance in estimating the value of state-action pair under policy can be reduced
217 by a factor of (1 p²,a) when the low-fidelity data is exploited, although the budget of high-fidelity
218 samples remains the same. Notice that
Cov [ (8 a), 2n (T()"),, Cov|
1 n
Cov [
(11)
n
because G.¹h 9 independent r.s. Vi F Hence, Cov ( (shi a), Q (T (s"
(s")),
a)].
Var @2tt (s"i, a)) and Var (T(")(((ss))))) can be estimated in practice based on the return
220
data samples using the standard unbiased estimators for the variance and covariance.
The reduced- variance estimator of 7 can be used to design a multifidelity Monte Carlo RL algorithm as shown in Algorithm/ in Appendix A. This algorithm is based on the on on-policy first-visit MC control algorithm with c-soft policies [34] but uses the multifidelity estimator (7). Algorithm is
222
223
224
based on the idea of generalized policy iteration. In the policy evaluation step (lines 1 11-18), the state-action value function is made consistent with the current policy by updating the estimated estimator (line 18). This update requires the estimation of the correlation between the low- and high- fidelity returns, which is done in lines 13-17. Next, in the policy improvement step (lines 19-20), the policy is made e-greedy with respect to the current state-action value function. In each episode, the agent needs to evaluate the policy in the low-fidelity environment to obtain Q This can be done in practice by collecting a large number of m return samples from the cheap low-fidelity environment and setting (T (s")), z e-greedy policy, ope along with its corresponding QMFMC, is guaranteed under the same conditions that guarantee convergence for the on- on-policy first-visit MC control algorithm with e-soft policies (34). In the following subsection, we theoretically analyze the impacts of variance reduction on policy evaluation and policy improvement.
226
long-term discounted returns of state-action pair (st, a.) using the control-variate-bnn
228
230
232
233
(T(shi), (,
a). The convergence of Algorithm to the optimal
234
235
236
237
238
3.3
Theoretical analysis
In this subsection analyze the impacts of variance reduction on policy evaluation error and policy improvement by introducing two main theorems. Intermediate lemmas along with all the proofs can be found in Appendix B.
240
242
3.3.1 Policy evaluation
243
In policy evaluation, the task is to estimate the state-action value function of given policy m. Trajectory samples are first generated by interacting with the environment using n, and the state-action value function is then estimated using either the single high-fidelity estimator (5) or the proposed multifidelity estimator 7 To analyze the impacts of variance reduction on policy evaluation error,
245
247
we first derive a a Bernstein-tyre type concentration inequality [6] that relates the deviation between the sample average and the true mean to the sample size n, estimation accuracy parameters E, and the variance of a r.V. as follows.
249
250
Let X2, Xn, be i.i.d. F.V.. with mean E[X;] = Px and variance E((X;- fx ) Vi E [n]. Furthermore, suppose that X,, Vi, are bounded almost surely with a parameter namely, Pr([X; Mxl 5 b) Vi. Then
Lemma
251
252
-n
Pr
Σ X1
- ux
2
< 2exp
(12)
71
102
1=1

---

253 for 0 5SES 0////
Next, the concentration bound of Lemma is used to derive the minimum sample size that is required ensure that the sample average deviates by more than & from the true mean with high probability 256 for both the high-fidelity estimator ( and the multifidelity estimator
254
257
Theorem To guarantee that
1. Pr(1Q (st,,a - 55) 2 1 - 8, then n 2 10 .0) log
2. Pr Pr(10MFMCC (s, Q a)l -E) 2 1 8, then 1(1-02 Do 10g(3)
The result of Theorem highlights the benefit of using our proposed multifidelity estimator 7 for policy evaluation as opposed to using the single high-fidelity estimator of ( By leveraging the correlation between low- and high-fidelity returns Pr.a, the variance of the multifidelity estimator is reduced by factor of p².a); which makes it possible achieve low estimation error at reduced number of high-fidelity samples.
260
261
262
264
265
3.3.2
Policy improvement
286
In policy improvement, new policy n' is constructed by deterministically choosing the greedy action with respect the state-action value function of the original policy тT, Q (s. a). every state, that is, n' rss)) = argmax (s, Vs E S. By the policy improvement theorem, n' is as good as or aEAA
267
better than æ under the assumption that ( a), Vs, a computed exactly. In practice, the MDP is unknown, and the state-action value function is estimated based on a finite number of trajectories. e-soft
269
270
exploratory policy, such policy. Because we are interested in studying how different estimators impact policy improvement, we consider target state Iع E Shi and assume that we have n trajectories for each action a A at this target state. This assumption basically ensures that all actions at the target state S have been explored equally well and enables us to make fair comparisons about estimator performance.
Moreover, those trajectories are generated by following
272
273
274
275
Without loss of generality, suppose that (si a1) 2 (shi,
(eaai.))) 02) 2 ... Qsi a(A))- Let A; =
276
Q (shi (1) (shi aa),, vi # 1. We analyze the probability that a1, which is the greedy action given the true Q (shh,, a). is the greedy action with respect to the single- and multifidelity estimators
277
278
279
in our next theorem.
Theorem Suppose that the number of trajectories from a state-action pair at a target state shi E Shi is the same for all actions E A and that 01 is the greedy action with respect to the true Qt a). Furthermore, suppose that phi (shil ss" a) N B(s"),, Vi E Shi Then
280
282
1. Pr(a1 aargmax Qm.n(s"..)) 2 II A
A² Var Qu Qu (stt,a,))
283
A Vari (a (o
aEA
2. Pr(a1 arrgaax QMEMC (sM, .)) 2 11 1)+ War Qu (* as) a+))++(11111+ (1-13.1,)))))) p3.., Wor(Q as")
A7
284
aEAA
285
Notice that when |ps.zl 1, the lower bound in the result of Theorem 2 approaches 1, which means that the correct greedy action can be selected with certainty when the reduced-variance multifidelity estimator (7) is adopted. Combining the results of Theorems and 2, the proposed MFMCRL algorithm is expected to outperform its single high-fidelity Monte Carlo counterpart in terms of learning a better policy under a given budget high-fidelity environment interactions.
287
289
4 Numerical experiments
In this section we empirically evaluate the performance of the proposed MFMCRL algorithm on synthetic MDP problems and NAS use case. Our codes and all experimental details can be found in Appendix C.
252
7

---

294
4.1
Synthetic MDPs
295
We synthesize multifidelity random MDP problems with state space cardinality |S| and action space cardinality |A]. The high-fidelity transition and reward functions, phi and Rl, respectively, are first generated based on random process as detailed in Appendix C.2. Next, for given phi and Rhi the corresponding plow and Rlo are generated by injecting Gaussian noise to meet a desired signal-to-noise ratio. Specifically, we generate random matrix Py of size [S] x |A| x [S] from a normally distributed r.v. with mean 0 and variance oz and set plow = phi + PN- plow is then
296
296
300
appropriately normalized so that Ex'es (lo(s (s a) = 1. Similarly, we generate random matrix RN of size |S] x |A| from a normally distributed r.v. with mean O and variance oi and set Rlow = Rhi + -NN- Phi and Rhi are then encapsulated within a gym-llik environment with which the agent can interact by exchanging sample tuples of the form (s"t, a, r" shi'). Similarly, plo and Rlo are encapsulated within gym-like environment to form the low-fidelity environment. In this experiment, both low- and high-fidelity environments share the same sate-action space- that is, T is an identity transformation- -yet the transition and reward functions of the low- low-fidelity environment are different since they are corrupted with noise. Notice that even if the agent could draw an infinite number of samples from pl and Roo it would not able to recover phi and Rhi since plo and Rh underneath the low-fidelity environment themselves are corrupted. This situation mimics what 310
301
302
303
304
305
306
307
309
311
happens in practice when we attempt to learn ple and Rhe based on real data and build an RL environment off those learned functions to train the agent.
312
313
After constructing the multifidelity environments, we train an RL agent using the proposed MFMCRL algorithm over 10K high-fidelity episodes, where a training episode is defined to be a trajectory that ends a terminal state. The MFMCRL agent interacts with the low-fidelity environment as shown in Algorithm 1, to generate
314
315
316
-vaiiane estimates of the state-action value function. As baseline for comparison, we train another RL agent (MCRL) using the standard the first-visit MC control algorithm over 10K high-fidelity episodes [34]. We set y and to 0.99 and 0.1, respectively. Every 50 training episodes. the greedy policy w.r.t to the estimated Q function is used to test the performance of the agent on 200 test episodes. We repeat the whole experiment with 36 different random seeds (to fully leverage our 36 core machine) and report the mean and standard deviation (across different seeds) of the test episode rewards in Figure 2 a). One can observe that for a given budget of high- fidelity episodes, the proposed MFMCRL algorithm outperforms MCRL in terms of policy performance,
317
319
321
323
with performance improving the RL agent collects more low-fideliyy samples (#T refers to the number of low-fides low-fidelity trajectories started from a state-action pair). In Figure 2b)). we vary the SNR of the low-fidee fow-fidelity environment and observe that performance improves as SNR increases. This is expected because the low- and high-fidelity environments are better-correlated at higher SNRs. Notice that when the SNR of the low-fidelity environment is -10 dB, there is no benefit from doing multifidelity RI. The reason is that the low- and high-fidelity environments are too weakly correlated
325
327
328
329
330
0.275 = 0.33, and Rh R = 1. 1.029 + 0.024, compared with the other extreme case (SNR +3dB) for which a. || || 0.009 = 0.0002, and [ R= 0.230 + 0.006. This is also evident in Figure 2 l). where we show the mean variance reduction factor VarlQ //ar QQi estimated based off the last 1K training episodes. When the low- low-fidelity environment is less noisy (higher SNR),
benefit from multifidelity estimation. In fact, for this case ..,.. [ |
E.
333
334
335
more variance reduction can be attained.
4.2 NAS
337
In NAS, the task is to discover high- segghheeffrmingg neural architectures with respect a given training dataset over a predefined search space. While many earlier works attempted to design RI--based NAS
338
339
algorithms, 3 40 [3], it has since become clear that the sample complexity of RL is too high to be
340
competitive with state-of- of-the--rtttttttt NAS methods [4] (3]. In this experiment we study how multifidelity
341
RL can improve learning in NAS over standard RL, which could serve to catalyze future work in this direction to make RL. more competitive in NAS.
342
For this experiment we use the tabular dataset of NAS-Bench-201 10 to construct multifidelity RL environments as detailed in Appendix C.3. In summary, the RL agent sequentially configures the nodes of an architecture (inducing MDP), after which the architecture trained on the training dataset for L epochs, and the validation accuracy on a held-out validation data set is provided to the
344
345
346
347
agent as reward. By maximizing the total rewards, high-performing architectures can be discovered.
348
TAS-Bench-201 reports the validation accuracy curves for all the architectures in the search space
8

---

0.5
Text Rewards
0.6
0.4
MCR
0.4
PIXER - an
MEMAA
0.2
1PVen 2-1h 100n=
PPXE2 200 am
0.5
MENCCA 081 +330)
MEMERL 5.00
2000 4000
6000 8000 10000
2000
4000
6000
8000
10000
-10d0
-bd08
-JoB
220B
Training Episode
Training Episode
SNR of low fow-fidolity environment
(a) _ has an SNR of -3dB
(b) # (0/(((s"))))))
(c) Variance reduction factor
Figure 2: Mean and standard deviation of test episode rewards for the proposed MFMCRL during training: (a) test episode rewards improve with increasing number of low-fidelity samples (#r"); (b) test episode rewards improve with less noisy low-fidelity environments; (c) variance reduction factor improves when low- and random MDP with |S| = 200, |A| 8.
environments
correlated. These results based
40
349 as a function the number of training epochs and for three image data sets. We construct two multifidelity scenarios as follows. In both sce- narios, the validation accuracy of an architecture at the end of training (i.e. at = 200 epochs) is used high-fida high-fidelity reward in the high-fidelity environment. For the low-fidelity environment, we have two cases: (i) low-fidelity environment is identical to the high-fidelity environment ex- cept for the reward function, which is now the validation accuracy at the L = 10th training
Test Rewards
39
351
38
353
37
MCRL MFMCRL-Case [I]
355
36
MFMCRL-Case (R]
358
0
2000 4000 6000 8000 10000 Training Episode
357
358
359
Figure 3: Mean and standard deviation of test episode rewards for the proposed MFMCRL dur- ing training on multifidelity NAS environments. See text for deseription of the two multifidelity scenarios (i) and (ii). In both cases, # (s)))))))))
360
epoch, and (ii) low-fidelity environment de- fined for a smaller search space and the reward function the validation accuracy of an archi- tecture at the I. = 10th training epoch. Note that in case (ii) the state space and dynamics differ between the low- and high-fidelity envi-
362
364
366
ronments. For both cases, we train both our proposed MFMCRL and the MCRL exactly as we did in Section 4.1 1, and we report the mean and standard deviation of test episode rewards in Figure 3 We can observe that our multifidelity RL framework does indeed improve over standard RL and that performance gains higher when the low- and high- high-fidelity environments more similar, case (i).
368
Conclusion
370
371 In this paper we have studied the RL problem in the presence of a low- and a high-fidelity environment for a given control task, with the aim of improving the agent's performance in the figh-iideiity
372
373
environment with multifidelity data. We have proposed a multifidelity estimator based on the method of control variates, which uses low-fidelity data reduce the variance in the estimation of the late-action value function. The impacts of variance reduction on policy improvement and policy evaluation are theoretically analyzed, and multifidelity Monte Carlo RL algorithm (MFMCRL) is
374
375
376
377
devised. We show that for a finite budget of high-fidelity data, the MFMCRL agent can well exploit the
378
cross-correlations between low- and high-fidelity data and yield superior performance. our future work, we will study the design of a control-variatebbasee multifidelity RL framework with function approximation to solve continuous state-action space RL problems.
380
Broader impact
381
382
Positive impacts: The energy/cost associated with generating low-fidelity data is generally much smaller than that of high-fidelity data. By leveraging low-fidelity data to improve the learning RL agents, greener agents are realized. Negative impucts: Running multifidelity RL agent training with weakly-correlated low- and high-fidelity environments can be wasteful of resources since the benefits in this case not significant.
385
385

---

References
387
388
[1] Pieter Abbeel, Morgan Quigley, and Andrew Y Ng. Using inaccurate models in reinforcement learning. In Proceedings of the 23rd international conference on Machine Learning, pages 1-8, 2006.
389
390
391
[2] Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
382
[3] Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network architectures using reinforcement learning. arXiv preprint wrXiv:/61..021600 2016.
393
[4] Prasanna Balaprakash, Romain Egele, Misha Salim, Stefan Wild, Venkatram Vishwanath, Fangfang Xia, Tom Brettin, and Rick Stevens. Scalable reinforcement-leaming architecture search for cancer deep learning research. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-33, 2019.
395
neural
397
389
[5] Richard Bellman. A Markovian decision process. Journal of Mathematics and Mechanics, 6(5):679-684, 1957.
400
401
[6] S.N. Bernstein. On a modification of Chebyshev's inequality and of the error formula of Laplace. Ann. Sci. Inst. Sav. Ukraine. Sect. Math. 4(5), 1924.
402
403
Dimitri P Bertsekas et al. Dynamic programming and optimal control: Vol. 1. Athena Scientific Belmont, 2000.
404
[8] Yevgen Chebotar, Ankur Handa, Viktor Makoviychuk, Miles Macklin, Jan Issac, Nathan Ratliff, and Dieter Fox. Closing the sim-to-real loop: Adapting simulation randomization with real world experience. In 2019 International Conference Robotics and Automation (ICRA), pages 9973-8979. IEEE, 2019.
406
408
[9] Mark Cutler, Thomas J Walsh, and Jonathan P How. Real-world reinforcement learning via multifidelity simulators. IEEE Transactions on Robotics, 31 (1 2015.
410
[10] Xuanyi Dong and Yi Yang. NAS-Bench-201: Extending the scope of reproducible neural architecture search. arXiv preprint arXiv:200/.00:20 2020.
412
413
[11] M Giselle Femnndez--oodino Chanyoung Park, Nam-Ho Kim, and Raphael Haftka. Review of multi-fidelity models. arXiv preprint arXiv:1609.07111 2016.
414
415
[12] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1861-1870, PMLR, 10-15 Jul 2018
416
417
419
[13] Yesmina Jaafra, Jean Lue Laurent, Aline Deruyver, and Mohamed Saber Naceur. A review of rete--eiinorremmen learning for deep neural networks architecture search. arXiv preprint arXiv:1812.07995, 2018.
421
423
[14] Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model- based policy optimization. Advances Neural Information Processing Systems, 32:12519- 12330, 2019.
425
[15] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning.
426
427
In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
428
[16]
Lodewijk Kallenberg, Markov decision processes. Lecture Notes. University of Leiden, 2011.
[17] Michael Kearns, Yishay Mansour, and Andrew Y Ng. A sparse sampling algorithm for near-
430
optimal planning large Markov decision processes. Machine Learning, 1932)2193-208, 2002.
10

---

432
[18] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, and Prasanna Balaprakash. Learning to optimize variational quantum circuits solve combinatorial problems. AAAI, pages 2367-2375, 2020.
433
[19] Phaedon-Stelios Koutsourelakis. Accurate uncertainty quantification using inaccurate computa- tional models. SIAM Journal on Scientific Computing, 31(5):374-3300, 2009.
436
437
[20]
Christiane Lemicux. Control variates. Wiley StatsRef: Statistics Reference Online, pages 1-8,
2014.
[1
Shibo Li, Wei Xing, Robert Kirby, and Shandian Zhe. Multi-fidelity Bayesian optimization via deep neural networks. Advances in Neural Information Processing Systems, 33, 2020.
440
441
[22] Timothy P Lillicrap. Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint 100iv:559.0020
443
2015.
444
[23] Timothy A Mann and Yoonsuck Choe. Directed exploration in reinforcement learning with transferred knowledge. In European Workshop on Reinforcement Learning, pages 59-76. PMLR, 2013.
445
448
447
[24] Xuhui Meng and George Em Karniadakis. A composite neural network that learns from multi- fidelity data: Application to function approximation and inverse PDE problems. Journal of Compulational Physics, 401:109020, 2020.
448
[25] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland. Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-553 -53,,,533333333 2015.
451
[26] Benjamin P Moster, Thorsten Naab, Magnus Lindström, and Joseph A O'Leary. GelaxyNet: connecting galaxies and dark matter haloes with deep neural networks and reinforcement learning in large volumes. Monthly Notices of the Royal Astronomical Society, 507(2):215-
454
456
2136, 2021.
457
[27] Benjamin Peherstorfer, Karen Willcox, and Max Gunzburger. Optimal model management for multifidelity Monte Carlo estimation. SIAM Journal on Scientific Computing, 38(5):A3163- A3194, 2016.
458
459
480
[28] Benjamin Peherstorfer, Karen Willcox, and Max Gunzburger. Survey of multifidelity methods uncertainty propagation, inference, and optimization. Siam Review, 60(3):550-591 2018.
461
462
[29]
Paris Perdikaris, Maziar Raissi, Andreas Damianou, Neil D Lawrence, and George Em Karniadakis. Nonlinear information fusion algorithms for data-efficient multi-fidelit mod- elling. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 473(2198):20) 60751, 2017
464
[30] Julian Schritwwesser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering Atari, Go, chess and shogi by planning with a learned model. Nature, 588(7839):604-609, 2020.
467
489
470
[31] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on Machine Learning, pages 1889-1897. PMLR, 2015.
472
473
[32] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
474
475
[33] Varun Suryan, Nahush Gondhalekar, and Pratap Tokekar. Multifidelity reinforcement learning
476
with Gaussian processes: -ased and model-free algorithms. IEEE Robotics & Automation Magazine, 1772)117--128 2020.
477
[34] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT Press, 478
2018.

---

480
[35]
Matthew E Taylor and Peter Stone. Transfer learning for reinforcement learning domains: A survey, Journal of Machine Learning Research, 10(7), 2009.
481
482
[36] Matthew E Taylor, Peter Stone, and Yaxin Liu. Transfer learning via inter-task mappings for temporal difference learning. Journal of Machine Learning Research, 8(9), 2007.
483
494
[37] Colin White, Willie Neiswanger, and Yash Savani. Bananas: Bayesian optimization with neural architectures for neural architecture search. arXiv preprint arXiv: 1858,, 1(2)44, 2019.
485
486
[38] Christopher K Williams and Carl Edward Rasmussen. Gaussian processes for machine learning. volume 2. MIT Press, Cambridge, MA, 2006.
488
[39]
Zhuangdi Zhu, Kaixiang Lin, and Jiayu Zhou, Transfer learning in deep reinforcement learning: A survey. arXiv preprint wwXiv:2009.07888 2020.
490
[40] Barret Zoph and Quoe V Le. Neural architecture search with reinforcement learning. arXiv preprint arXiv:161..0157,, 2016.
481
Checklist
492
495
1. For all authors...
494
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Figure 1.
485
(b) Did you describe the limitations of your work? [Yes] Refer to Section 4.1
497
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Refer to Section 6.
498
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
500
501
2. If you are including theoretical results...
502
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Refer to the theorem statements in Section 3.3.
504
(b) Did you include complete proofs of all theoretical results? [Yes] Refer to Appendix B.
505
3. If you ran experiments..
508
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] Our codes are included in the supplemental materials and will be shared online after decision is made on the manuscript.
507
508
509
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Refer to Section 4 and Appendix C.
511
512
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Figures 2 and
513
514
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Refer to Appendix C.I.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Refer to Section 4.2.
(b) Did you mention the license of the assets? [No] The dataset used in this work is publicly available under the MIT License.
519
(c) Did you include any new assets either in the supplemental material or as URL? [No] Synthetic data used Section 4.1 can regenerated by using the codes we provided.
521
522
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
523
524
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
12

---

527
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
528
829
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount
532
spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "rtaOqnEl5u", "reviewer": "Reviewer_8Vzs", "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. \n ", "questions": "## Preliminaries and related work\n1. \"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).\n2. \"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).\n3. \"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. \n4. \"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?\n5. 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.\n \n## Multifidelity estimation in RL\n\n1. \"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?\n2. \"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? \n3. 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?\n4. 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? \n5. \" 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.  \n\n## Numerical experiments\n1. 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. \n2. What were the relative clock-times of NAS with and without the control-variate schemes? Were they comparable?\n3. 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? \n\n## Citations mentioned\n(1) Bertsekas, Dimitri. Reinforcement learning and optimal control. Athena Scientific, 2019.\n\n(2) https://people.cs.umass.edu/~barto/courses/cs687/williams92simple.pdf\n\n(3) https://proceedings.neurips.cc/paper/2010/file/35cf8659cfcb13224cbd47863a34fc58-Paper.pdf\n\n(4) https://arxiv.org/pdf/1506.02438.pdf \n\n(5) https://arxiv.org/abs/1710.06542\n\n(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. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## General Comments\nI 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. \n\n## Strengths\n1. This is actually a really clearly written paper that I enjoyed reading.\n2. I think that the area that it considers is an important one.\n3. The experiments are clearly presented, and the weaknesses of the work, as well as their strengths are discussed in detail. \n\n## Weaknesses\n1. 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. \n2. 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. \n3. 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. \n4. 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? \n5. 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). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "N96Sf55YH9", "reviewer": "Reviewer_HcCy", "summary": "\nThe 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.\n", "questions": "Can the authors provide a more precise description of the i != j covariance construction and why the indexes should match up?\n\nWhy is the analysis restricted to only domains with terminal states?\n\nCan 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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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:\n\nMore precise terminology needed:\nThe 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?\n\nI 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.\n\nThe sentence starting on line 120 could use a citation.\n\nLine 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.\n\nI 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. \n\nOn potential disadvantages with regards to previous methods:\nI 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IwI9geZUTkt", "reviewer": "Reviewer_rJ7u", "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.", "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:\n\n- 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?\n\n- 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?\n\n- 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.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\n- [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)\n\n- [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?\n\n- [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?\n\n*Overall*\nThe 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).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject