Frequency-based Search-control in Dyna
Authors: Yangchen Pan
Jincheng Mei
Amir-massoud Farahmand
Venue:  (2020)
Keywords: Model-based reinforcement learning
search-control
Dyna
frequency of a signal

Abstract: Model-based reinforcement learning has been empirically demonstrated as a successful strategy to improve sample efficiency. In particular, Dyna is an elegant model-based architecture integrating learning and planning that provides huge flexibility of using a model. One of the most important components in Dyna is called search-control, which refers to the process of generating state or state-action pairs from which we query the model to acquire simulated experiences. Search-control is critical in improving learning efficiency. In this work, we propose a simple and novel search-control strategy by searching high frequency regions of the value function. Our main intuition is built on Shannon sampling theorem from signal processing, which indicates that a high frequency signal requires more samples to reconstruct. We empirically show that a high frequency function is more difficult to approximate. This suggests a search-control strategy: we should use states from high frequency regions of the value function to query the model to acquire more samples. We develop a simple strategy to locally measure the frequency of a function by gradient and hessian norms, and provide theoretical justification for this approach. We then apply our strategy to search-control in Dyna, and conduct experiments to show its property and effectiveness on benchmark domains.

Published as a conference paper at ICLR 2020
FREQUENCY-BASED SEARCH-CONTRON IN DYNA
Yangchen Pan & Jincheng Mei Department of Computing Science University of Alberta Edmonton, AB, Canada
Amir-massoud Farahmand
Vector Institute & University of Toronto Toronto, ON, Canada fa Barahmannd@recttornsstttttt
{pan6, jmei2 wew.euulabara.cmmm ca
ABSTRACT
Model-based reinforcement learning has been empirically demonstrated as suc- cessful strategy to improve sample efficiency. In particular, Dyna is an elegant model-based architecture integrating learning and planning that provides huge flexibility of using a model. One of the most important components in Dyna is called search-control, which refers to the process of generating state or state-action pairs from which we query the model to acquire simulated experiences. Search- control is critical in improving learning efficiency. In this work, we propose sim- ple and novel search-control strategy by searching high frequency regions of the value function. Our main intuition built on Shannon sampling theorem from sig- nal processing, which indicates that high frequency signal requires more samples to reconstruct. We empirically show that high frequency function is more diffi- cult to approximate. This suggests a search-control strategy: we should use states from high frequency regions of the value function to query the model to acquire more samples. We develop a simple strategy to locally measure the frrequency of a function by gradient and hessian norms, and provide theoretical justification for this approach. We then apply our strategy to search-control in Dyna, and conduct experiments to show its property and effectiveness on benchmark domains.
INTRODUCTION
Model-based reinforcement learning (MBRL) (Lin, 1992; Sutton, 1991b; Daw, 2012: Sutton & Barto, 2018) methods have successfully been applied to many benchmark domains (Gu et al., 2016; Ha, David and Schmidhuber, Jürgen, 2018; Kaiser et al., 2020). The Dyna architecture, introduced by Sutton (1991a), is one of the classical MBRL architectures, which integrates model-free and model-based policy updates in an online RL. setting (Algorithm in Appendix A.3). At each time step, Dyna agent uses the real experience to learn model and to perform model-free policy up- date, and during the planning stage, simulated experiences are acquired from the model to further improve the policy. A closely related method in model-free learning setting is experience replay (ER) (Lin, 1992; Adam et al., 2012), which utilizes a buffer to store experiences, An agent using the ER buffer randomly samples the recorded experiences at each time step to update the policy. Though ER can be thought of as a simplified form of MBRL (van Seijen & Sutton, 2015), a model provides more flexibility in acquiring simulated experiences.
crucial aspect of the Dyna architecture the search-control mechanism. is the mechanism for selecting states or state-action pairs to query the model in order to generate simulated experiences (cf. Section 8.2 of Sutton & Barto 2018). We call the corresponding data structure for storing those states or state-action pairs the search-control queue. Search-control is of vital importance in Dyna, as it can significantly affect the model- based agent's 's sample efficiency. A simple approach to search- control to sample visited states or sate-action pairs, i.e., use the initial state-action pairs stored in the ER buffer the search-control queue. This approach, however, does not lead to an agent that outperforms a model-free agent that uses ER. To see this, consider deterministic environment, and assume that have the exact model. If we simply sample visited state-action pairs for search- control, the next-state and reward would be the same as those in the ER buffer, In practice, we have
"Equal contribution.

---

Published as a conference paper at ICLR 2020
model errors too, which causes some performance deterioration (Talvitie, 2014; 2017). Without an elegant search-control mechanism, we are not likely to benefit from the flexibility given by a model.
Several search-control mechanisms have already been explored. Prioritized sweeping (Moore & Atkeson, 1993) is one such method that is designed to speed up the value iteration process: the sim- ulated transitions are updated based the absolute temporal difference error. It has been adopted to continuous domains with function approximation too (Sutton et al., 2008; Pan et al., 2018; Corneil al., 2018). Gu et al. (2016) utilizes local linear models to generate optimal trajectories through iLQR (Li & Todorov, 2004). Pan et al. (2019) suggest a method to generate states for the search- control queue by hill climbing on the value function estimate.
This paper proposes an alternative perspective to design search-control strategy: we can sample more frequently from the state space where the value function more difficult to estimate. We first review some basic background in MBRL (Section 2). Afterwards, we review some concepts in signal processing and conduct experiments in the supervised learning setting to show that a high frequency function is more difficult to approximate (Section 3). In order to quantify the difficulty of estimation, we borrow a crucial idea from the signal processing literature: a signal with higher frequency terms requires more samples for accurate reconstruction. We then propose method to locally measure the frequency of a point in a function's 's domain and provide a theoretical justification for our method (Theorem in Section 3.2). We use the hill climbing approach of Pan et al. (2019) to adapt our method to design a search-control mechanism for the Dyna architecture (Section 4). We conduct experiments benchmark and challenging domains to illustrate the properties and utilities of our method (Section 5).
2 BACKGROUND
Reinforcement learning (RL) problems are typically formulated as Markov Decision Processes (MDPs) (Sutton & Barto, 2018; Szepesvári, 2010). An MDP (S. TP I.P. R, 7) is determined by state space S, action space A, transition function TP, reward function R S x x S -> IR and discount action a, A.
factor 7 E [0, 1]. At each step t, an agent observes state s, 8, and takes The environment receives at, and transits to the next state St+1 ~ P(-]s,, at). The agent receives reward scalar rt+1 R(st, ae; 8t+1). The agent maintains a policy
S x A + [0, 1] that determines the probability of choosing an action at a given state. For a given state-action pair (s, a), the action-value function of policy π is defined Qx a) |S,, s, A, a; A4+ x]
where G2 Ei=o? "(R(s az, 8141) is the return of so, ag. $1, a1.... following the policy and transition P. Value-based RL methods learn the action-value function (Watkins & Dayan, 1992), and act greedily w.r.t. the action-value function. Policy-based RL methods perform gradient update of parameters to learn policies with high expected rewards (Sutton et al., 1999). Both value and policy-based RI. methods can be easily adopted in the Dyna framework.
Model-based RL. A model is mapping that takes state-action pair its input and outputs some projection of the future state. A model can be local (Tassa et al., 2012; Gu et al., 2016) or global (Ha, David and Schmidhuber, Jürgen, 2018; Pan et al., 2018), deterministic (Sutton et al., 2008) or stochastic (Deisenroth & Rasmussen, 2011; Ha, David and Schmidhuber, Jürgen, 2018), feature-to-feature (Corneil al., 2018; Ha, David and Schmidhuber, Jürgen, 2018) or observation- to-observation (Gu et al.. 2016; Pan et al., 2018; Kaiser et al., 2020), one-step (Gu et al., 2016; Pan al., 2018), or multi-step (Sorg& & Singh, 2010: Oh al., 2017), or decision-aware (Joseph al., 2013; Farahmand et al., 2017; Silver et al., 2017). Modelling the environment dynamics through reproducing kernel Hilbert space (RKHS) embedding has been also studied (Grunewalder al., 2012), where the Bellman operator is approximated in an RKHS. The model we consider in this work is a one-step environment dynamics model, which takes a state-action pair as its input and returns the next-state and reward. Our proposed search-control approach, however, can be naturally used for different types of models.
The most relevant work to ours is hill climbing Dyna (Pan et al., 2019). Pan et al. (2019) proposes a search-control mechanism based on hill climbing on the value estimates (see Algorithm 3 in Ap- pendix A.3). We briefly review the key steps of their algorithm, which is called (Hill Climbing)HC- Dyna, as it helps to understand ours. HC-Dyna maintains an ER buffer. At each step, a state is randomly sampled from the ER buffer and is used as the initial state to perform hill climbing (i.e.
2

---

Published as a conference paper at ICLR 2020
gradient ascent) the learned value function. The states along the trajectory stored in the search-control queue. During the planning stage, states are sampled from the search-control queue and are paired with their corresponding on-policy actions (i.e., actions selected by the current Q network at the sampled states). Afterwards, the model is queried for each of the state-action pairs to get the next-state and reward. These simulated transitions are then mixed with samples from the ER buffer, which are observed by the agent during its interaction with the real environment, to train the value function estimator, e.g., a deep neural network.
The heuristic idea behind the search-control mechanism of HC-Dyna is that the magnitude of the value function provides useful information for guiding where to query the model. This heuristic can intuitively be understood by noticing that an RL agent tends to move towards high-value regions of the state space; by performing gradient ascent on the (estimated) value function, we provide the agent with more samples from regions where it may move towards in the future. Even if the estimated value function is incorrect and the samples are indeed from the low-value regions of the state space, these extra samples lead to the fast correction of the estimated value in those regions. Nevertheless, the magnitude the value function is only one source of extra information from which design
mechanism. This work suggests a different perspective: we should sample more from the regions of the state space where learning the value function is more difficult.
3 UNDERSTANDING THE DIFFICULTY OF FUNCTION APPROXIMATION
In a regular regression setting, we illustrate that high frequency regions of a function is difficult to approximate. We show that by assigning more training data to those regions, the learning per- formance considerably improves. To make this insight practically useful, we employ the sum of gradient and hessian norms of a function tablish theoretical connection between our proposed criterion and the local frequency of function. This would be the foundation our frequency- search-control method in Section
measure of the local frequency of a function. We es-
3.1 WHAT TYPE OF FUNCTION IS DIFFICULT TO APPROXIMATE?
Consider the standard regression problem with the mean square loss. Given training set D ((2s, y:) Ji) our goal is to learn an unknown target function f*((x) = E|||X = x] by empirical risk minimization. Formally, we aim solve
1 (f(xs)) -v)
= arg min JEH n
1=1
where H. is some hypothesis space. Suppose that we can choose the distributions of samples {z,)- How should we select them in order to improve the quality of the learned function? One intuitive heuristic that if we know the regions in the domain of f that are more difficult to approximate, can assign more training data there in order to help the learning process. The important question how to quantify the difficulty of approximating a function. We borrow an idea from the field of signal processing to suggest a method.
The Nyquist-Shanee Shannon sampling theorem in signal processing states that given a hand-limited func- tion (or signal) R + E with the highest frequency (in the Fourier domain) of Wbandwidth- perfectly reconstruct it based on regular samples (in the time domain) obtained at the sampling rate of 22bamdwidth (Zayed, 1993).2 Therefore, if the Fourier transform of function has high frequency terms, more samples are required to reconstruct it accurately. We note that the sampling theory has been applied in the sample complexity analysis of machine learning algorithms (Smale & Zhou, 2004; 2005; Jiang, 2019). Although the problem setting in machine learning is somewhat different from this result in signal processing, it still provides a high-level intuition for us: regions with more high frequency signals require more learning data.
can
According to the original paper, natural gradient used to guarantce a certain level of coordinate invariance property, so it can handle state variables with vastly different numerical scales. Sampling rate refers to number of samples per second used to reconstruct continuous signals.
3

---

Published as a conference paper at ICLR 2020
To make this high-level intuition concrete, consider the following function:
(i (sn
x [-2,0),
ssin (2:
(1)
[0,
It is easy to check that the regions| [-2, 0) and [0, 2] contain signals with frequency ratio 8: 1. Based on the intuition from the sampling theorem, the [-2, 0) interval requires more training data than the [0, 2] interval. Given the same amount of training data, and the same learning algorithm, would expect that assigning more fraction of the training data on [-2, 0) to perform better than distributing them uniformly or assigning more samples to the [0, 2] interval.
An illustrative experiment. To empirically verify the intuition, we conduct a simple regression task, with fain the target function. The training set D {(2,, Hi) is generated by sampling x E [-2. and adding Gaussian noise N (0,, on Eq. (1), where the standard deviation is set to be 0.1. We present the l regression learning curves of training datasets with different biased sampling ratios ps E (60%, 70,, 80%). as shown in Fig. 1 (a)-(c). We observe that biased training data sampling ratios towards high frequency region clearly speeds up learning. This is consistent with the intuitive insight and suggests that our heuristic to assign more data to high frequency regions leads to faster learning.
Blased- low Blased-hip high Unblased
Blased low Blased-High
Biased-lov
0.50
6.22
Blased-niot
6.06
Unblased
Unblas
Root Square Error
Root
Mean
Square
Erro
Erro+
(50runs)
(50rung) Ca
(50rung)
18--85 1948 1-0-00
E20 Frests
Navest
1. seriss 25wh Number Perations
62-950 19 15e0es 78mm Euh
Fremt Number of Eerations
Number of Rerations
(a) Pb 60%
(b) pb 70%
(c) pb 80%
Figure 1: Testing error as a function of number of training data from the high frequency region [-2, 0) and is labeled Biased-high. We include unbiased training dataset as a reference (Unbiased). The total numbers of training data are the same across all experiments. The testing set is unbiased and the results are averaged over 50 random seeds with the shade showing standard error.
updates. pb = 60% means 60% of the
3.2 IDENTIPYING HIGH FREQUENCY REGIONS OF FUNCTION
Identifying the high frequency region of ssin in the previous toy problem was easy, as each region contained a signal with a constant known frequency. In practice, we face two main difficulties to identify the high frequency regions of function. The first is that we do not have access to the un- derlying target function, but only to data or possibly an approximate function that estimated using data, e.g., trained neural network. The second is that frequency is global property rather than local one. The value of the function at each (non-zero measure) region of the domain has impact on its global frequency representation. To make the high frequency heuristic practically useful, we need a simple criterion that (a) uses function approximation, (b) characterizes local frequency infor- mation, and (c) can be efficiently calculated. Inspired by the function sain in Eq. (1), natural idea
is to calculate the first order f((x) df(x) dr. or second order derivative f"(x: df f(a)) because they
dad
both satisfy (a) and (c). As "sanity check" for property (b), consider the following examples.
Example 1. For satn defined in Eq. (1), calculate the integrals of squared first order derivative f'an
on high frequency region| [-2,0) and low frequency region [0, 2). respectively:
S 1 (x)) dr = 64T?, [ (Iau((tt)) dx - n²
0
4

---

Published as a conference paper at ICLR 2020
Example 2. Let f: : T]] + R be band-limites real valued function defined
N
60
f(x)
On cos (nz) + bn sin (nx),
2
n=1
where ao, Ons bn E ERR n 1, 1,2.....
n Then, N are Fourier coefficients of frequency
2x"
N
N [")r"( dx Σ
[()) de do= = Σ n (a + b,),
n (an + bg)
Example 1 shows that the integral of squared first order derivative ratio is 64 : (the frequency ratio is 8 1). and the region with large derivative magnitude is indeed the high frequency region. Moreover, Example 2 indicates that for one dimensional real-valued functions over bounded do- main, the integral of derivative magnitude is closely related to the frequency information. For the squared derivative, the integral is the same as weighting the frequency terms a, and bn proportional to n²² and for the squared second-order derivative, the integral is the same as weighting the fre- quency terms proportional to n The weighting schemes n² or n emphasize the higher frequency terms.
Empirical demonstration. Our calculation in the above examples implies that regions with large gradient and Hessian norm correspond to high frequency regions. Based on the same spirit of the l2 regression task in Section 3.2, we empirically verify this insight. Our expectation is that biasing training dataset towards high gradient norm and Hessian norm would achieve better learning results. In Fig. 2(a).
corresponds uniformly sampling E [-2, 2] for 60% of training data and sampling proportional to gradient norm (i.c., p(x) x 1f (z)]) for the remain- ing 40%; while Biased-HessianNe
corresponds to sampling proportional to Hessian norm (i.e., p(x) x I.fain (r)] for the remaining 40% of training data. In Fig. 2(b) we visualize the two types of biased training points. Sampling according the gradient norm the Hessian norm leads to denser point distribution in the high frequency region [-2, 0): there are 65.35%, 68 18.9 of training points fall in [-2, 0J in Fig. 2(b), (c) respectively. An important difference between Fig. 2(b) and (c) is that, sampling according to Hessian norm leads to denser points around spikes: there are 18. 17% points fall in the yellow area in (b) and 27. 27.45% such points in (c). Those areas around spikes should be more difficult to approximate as the underlying function changes sharply, which explains the su- perior performance on the data set biased by Hessian norm. Fig. 2(a) shows that such biased training datasets provide fast learning, similar to the high frequency biased training datasets in Fig. 1.
Given a function f + y and a point x E X, we propose to measure frequency of f around a small neighborhood of (we call this local frequency) using the following function:
g(x) def [+)(2))) + | (z)]
where [x)]| is the fg-norm of the gradient x. and H (z), Hessian matrix of f at x. We claim that local frequency of f around x is proportional to g(z).We theoretically justify this claim. For real-valued functions in Euclidean spaces, our theory connects local gradient and Hessian norms, local function energy to local frequency distribution. The proof of our theorem and its connection to the well-known uncertainty principle are in Appendix A.2.
r is the Frobenius norm of the
Theorem 1. Given any function f R R. for any frequency vector k E TR,, define its local Fourier transform around x E R.
f(k) del
f(y) exp --2Tii y kb dy, 2Ti
vEB(o.1)
for local function around x, i.e. y E B(I,1) def {y l1y xl| < 1}. Assume the local function "energy" is finite,
[f(]] dy [ 00,
Vz E R".
(3)
vEB(
We consider the notion of energy in signal processing terminology: the energy of a continuous time signal (z(t) is defined (x))) dt. In our theory, function f is the signal.
5

---

Published as a conference paper at ICLR 2020
Define "local frequency distribution" of fz) as:
Ty(k) def [1
Ak E
(4)
JR [k
Then, for any E IR, we have: 1) The first order connection:
J [VS(W)I dy= 4m²
=4m=
[ Us(i) dy dol
1/ mT(()) ||211 dk ab..
(5)
2) The second order connection:
(1 (((I dul U (T(k) ||A|1 dk
JEERO..) [[Hr(W)l|ddy 16x
(6)
Remark Note that f defined in Eq. (4) is probability distribution over IR" as:
f (k)kk 1, and ④ 7 2 O, E
We use such a distribution characterize local frequency behaviour for reasons. First, comparing frequencies of regions is more naturally captured by distribution than one single scalar, since signals usually are within a range of frequencies. Second, eliminate the impact of the function energy Eq. (3), we normalize the Fourier coefficient I to get f..
Remark 2. For frequency vector k E RR" the larger its norm ||k]| is, the higher its frequency
is. Given any x and its local function (i.e., f(-) around x)), T is the proportion(percentue
that frequency k occupies. Therefore, the integral of π TT(k)) ||k] reflects the contribution of high frequency terms in the local frequency distribution of a function.
Remark 3. Consider f value function in reinforcement learning setting. Theorem I indicates that regions with large gradient norm can either have large absolute value function, or high local frequency, both. To prevent finding regions that only have large negative value function, our theory implies that it is reasonable to take both gradient norm and value function into account, as our proposed method does in the next section.
6:90
Gaased-GradientMorr HesslanNemm Uniiased
10
Root
my
Msan
0.0
0.8
150rune]
-10
-10
Number of Tberations
(a) RMSE vs. number of iterations (b) biased training points - Gradient (c) biased training points Hessian
We show the learning curve of the l2 regression on three training datasets in Figure (a) and show 1k points uniformly sampled from the two biased training data sets (b)(c) respectively. The total number of training data points are the same across all experiments. The yellow area includes all the spikes, and defined by restricting |gy 1.0 0.1. The testing set is unbiased and the results are averaged over 50 random seeds with the shade indicating standard error.
Figure 2:
4 FREQUENCY-BASER SEARCH-CONTREN IN DYNA
We present the Dyna architecture with the frequency- based search-control (Algorithm 1) in this sec- tion. combines the idea that samples from frequrrry regions of the state space is important,

---

Published as a conference paper at ICLR 2020
as discussed in the previous section, and the hill climbing process to effectively draw samples from those regions, as introduced by Pan et al. (2019). We omit implementation details such as precondi- tioning, noisy gradient for the hill climbing process, and refer readers to Appendix A.6 and A.7.
Our goal is to query the model more often from the regions of the state space where the local frequency of the value function is higher. The intuition behind this search-control mechanism, as discussed in the previous section in the context of supervised learning, is that those regions corre- spond where learning the (value) function is more difficult, hence more samples from the model might be helpful. To populate the search-control queue with states from those regions, we can do hill climbing on (s)) I| V (s)ll + [|H Theorem 1, however, suggests that states with large gradient norm can either have large absolute value, or high local frequency. or both. We want to avoid many samples from regions with large negative value states, as those states may be rarely visited under the optimal policy anyway. A sensible strategy to get around this problem is to com- bine the proposed hill climbing method with the previous hill climbing on the value function (Pan et al., 2019), as the latter tends to generate samples from high value states.
We propose the following method for combining those approaches. At each time step, with certain probability, we perform hill climbing by either
8 st Vsg(s) (.V(s)
with probability of with probability of -p
(7a)
(7b)
and store states along the gradient trajectory in the search-control queue. When hill climbing on the value function (7b), we sample the initial state from the ER buffer as suggested by the previous work (Pan et al., 2019). This populates the search-control queue with states from the high value regions of the state space. When hill climbing on g(s) (7a), however, we sample the initial state from the search-control queue itself (instead of the ER buffer). This way ensures that the initial state
for searching high frequency region has relatively high value. Hill climbing on g(s) from an initial
state with high value populates the search-control queue with high frequency samples around high
value regions of the state space, We discuss some other intuitive mechanisms that we have tested in Appendix A.4.
Similar to the previous work (Pan et al., 2019), we obtain the state-value function in both (7a) and (7b) by taking the maximum of the estimated action-value, i.c. V(s) max, Q(s, se max, Qo(s, a) where 0 is the parameter of the Q-network. Similar to the Dyna architecture (Algo- rithm 2), during planning stage, we sample multiple mixed mini-batches update the parameters (i.e. we call multiple planning steps/updates). The mixed mini-batch was also used in the work by Gu al. (2016) and can alleviate off-policy sampling issue as studied by Pan et al. (2019).
EXPERIMENTS
In the experiments, we carefully study the properties of our algorithm on the MountainCar bench- mark domain. Then we illustrate the utility of our algorithm on a challenging self-designed Maze- GridWorld domain, by which we illustrate the practical implication of having samples from the high frequency regions. Though we mainly focuses on search-control instead of how to learn a model, we include the result of using an online learned model for our algorithm. We refer readers to Ap- pendix A.5 for additional experiments and Appendix A.6 for the reproducibility detail.
5.1 UTILITY OF FREQUENCY-BASED SEARCH-CONTROL
The MountainCar (Brockman et al., 2016) domain is well-studied, and it is known that the value function under the optimal value function has sharp changing regions (Sutton & Barto, 2018), which the setting where our algorithm should be more effective. The agent needs to learn to reach the goal state within as few steps as possible since the reward is -1 per time step. The purposes of experimenting on this domain are: 1) verify that our search-control can outperform several natural competitors under different number of planning updates; 2) show that search-control is robust to environment noise.
We use the following competitors. Dyna-Frequency is the Dyna architecture using the proposed search-control strategy (Algorithm 1); Dyna- Value is Algorithm 3 from the previous work (Pan al., 2019); PrioritizedER is DQN with prioritized experience replay (Schaul et al., 2016); ER
7

---

Published as a conference paper at ICLR 2020
Algorithm Dyna architecture with Frequency-based search-control
B: the ER buffer, 33: search-control queue
M A + S x IR, the model outputs the next-state and reward
want fetch by hill climbing, d: number of planning steps ca: the threshold for accepting state
m: number states
Q': current and target Q networks, respectively
b: the mini-batch size, B E (0, 1): the proportion of simulated samples in mini-batch
r: update target network Q' every T updates to Q
t 0 is the time step, n, is the number of parameter updates
while true do
Observe 8t, take action de (i.e. c-greedy w.r.t. Q)
Observe $1+1, re+11 add (St, at, St+1, (o+1) to
// Gradient ascent hill climbing
With probability sample from B, choose rule (7a), or from otherwise; set c t 0, t-
choose hill climbing rule (7a) or (7b) respectively;
while < m do
update by executing the chosen hill climbing rule
if is out of state space then: // resample the initial state and hill climbing rule With probability p, 1 - p. choose hill elimbing rule (7a) or (7b) respectively; sample s from B, if choose (7a), or from B otherwise; set +- 0,
continue
if ||s $ $112/ V ca then: // n is the state dimension, i.e. S C R"
add to B., $ s,c +++
for d times do // d planning updates: sample mini-batches
draw 35 sample states from the search-control queue B,, pair them with their correspond- ing on-policy action, and query .M to get the corresponding next-states and rewards draw (1 - B)b sample transitions from the ER buffer B and add them to the simulated transitions
use mixed mini-batch for parameter update of the estimator, egg., DQN n, n2 +1 mod (n,, == then:
Q' Q
t+1
is simply DQN with experience replay (ER) (Mnih et al., 2015). Figure 3 shows the learning curves of all those algorithms using 10 planning updates (a)(b) and 30 planning updates (c)(d) un- der different stochasticity. In Figure 3(b)d), the reward is sampled from the Gaussian distribution N(-1,o"), a (0.0, 0.1).
We make several important observations: 1) With increased number of planning updates, these algorithms do not necessarily perform better, shown in Figure 3(c). The proposed algorithm, however, appears to gain more through more number of updates since the difference between Dyna- Frequency and Dyna- Value seems to be clearer in Figure 3(c) than in Figure 3(a). 2) Since both Dyna- Value and our algorithm fetch the same number of states (i.e. m 20) by hill climbing, the superior performance our algorithm indicates the advantage of using samples from the high frequency regions. 3) PrioritizedER clearly performs worse than algorithm and Dyna-Value, which probably implies the utility of the generalization power of the value function to acquire ad- ditional samples. 4) Our algorithm maintains superior performance in the presence of noise. One reason is that, noisy perturbation leads to more "energy" in all frequencies. When taking derivative, those high frequency terms amplified. Hence, remains while the value estimate itself may get affected in an unpredictable manner.
with perturbation, high frequency region
5.2 A CASE STUDY: MAZEGRIDWORLD
We now illustrate the utility of our method challenging MazeGridWorld domain shown in Figure 4(a). The domain has continuous state space S = [o, 1]2 and four discrete actions (up, down, left, right). There are three walls in the middle, each of which has hole for the agent
8

---

Published as a conference paper at ICLR 2020
-250-
Oye
-253
-500
503
of
Estedo
1150
-2000
2.0 18me strps
2.3
(a) plan steps 10. 0 (b) plan steps 10, 0.1 (c) plan steps 30, (d) plan steps 30. 0.1
Figure 3: Evaluation curves (sum of episodic reward v.s. environment time steps) of Dyna-Valus PrioritizedER. Dyna-Frequency. ER on MountainCar with different number of planning updates with different reward noise variance. Notice that the dashed line denotes the evaluation curve of our algorithm with an online learned model. a = indicates the original deterministic reward. All results are averaged over 30 random seeds.
to go through. Each episode starts from the bottom left and ends at top right and the agent receives a reward of -1 each time step, hence the agent should learn to few steps possible to reach the goal area. On this domain, we mainly study our algorithm and the Dyna-Value Value algorithm.
Figure 4(b) shows the evaluation curves of the algorithms. An important difference between algorithm and the previous work is in the variance the evaluation curve, which implies a robust policy learned our method. In Figure 5, further investigate the state distribution in search- control queues of the two algorithms by uniformly sampling 1000 states from the two queues. Notice that a very important difference between the distributions that our search-contre queue has clearly high density around the bottleneck area, i.e., the hole areas where the agent can go across the walls. Learning stable policy around such areas is extremely important: the agent simply fails to reach the goal state if they cannot pass any one of the holes. This distinguishes our algorithm with the previous work, which appears to acquire states near the goal area.
HI HL
G
-250
-500 Sum of rewards per Episode (30runs)
Dyna-Value Dyna- rena-Frequency
-1750
-200g
0.6
0.8
S
time steps
1e5
(a) MazeGridWorld
(b) Episodic reward vs. time steps
Figure 4: (a) is visualization of the MazeGridWorke domain. (b) shows evaluation curves of Dyna-Value and Dyna-Frequency. Dashed line indicates using an online learned model of our algorithm. All results are averaged over 30 random seeds.
DISCUSSION
We motivated and studied new category of methods for search-control by considering the approx- imation difficulty of function. We provided method for identifying the high frequency regions of a function, and justified it theoretically. We conducted experiments to illustrate our theory. We in- corporated the proposed method into the Dyna architecture and empirically investigated its benefits. The method achieved competitive learning performances on a difficult domain.
There several promising future research directions. First, it is worth exploring the combination of different
strategies. Second, we can explore the use active learning methods (Set- tles, 2010; Hanneke, 2014) in the design of search-control mechanisms, since active learning

---

Published as a conference paper at ICLR 2020
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.0
0.2
0.8
1.0
(a) frequency-basee search-control states
(b) value-based search-control states
The state distribution in the search-control queue of our algorithm Dyna-Frequency (a) and Dyna-Value (b) at 50k environment time step. Each blue shadow area is 0.1 x 0.1 square indicating the hole where the agent can go through the wall. Our search-control queue has a state distribution with high density around those squares. In (a), there are 25.3% points fall inside 0.1 radius ball centered at each square in total; in (b), there are 11. 11.7% such points. The black box on the top right is the goal area.
Figure 5:
cerns about learning a function with as few samples as possible. This directly corresponds to our main purpose of using smart search-control method in Dyna: to improve policy by using few planning steps as possible.
ACKNOWLEDGMENTS
We would like thank the anonymous reviewers for their helpful feedback. Amir-massoud Farah- mand acknowledges the funding from the the Canada CIFAR AI Chairs program. Yangchen Pan acknowledges the funding from Amii.
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, and et al. TensorFlow: Large-scale machine learning heterogeneous systems. Software available from tensorflow.org. 2015.
Sander Adam, Lucian Busoniu, and Robert Babuska. Experience replay for real-time reinforcement learning control. IEEE Transactions on Systems, Man, and Cybernetics, pp. 201 201-212, 2012.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. OpenAl Gym. arXiv:1606.01555 2016.
Dane S. Corneil, Wulfram Gerstner, and Johanni Brea. Efficient model-based deep reinforcement learning with variational state tabulation. In International Conference Machine Learning, pp. 1049-1055 2018
Nathaniel Daw. Model-based reinforcement learning as cognitive search: Neurocomputational theories. Cognitive search: Evolution, algorithms and the brain, 2012.
M Deisenroth and C E Rasmussen. PILCO: A model-based and data-efficient approach to policy search. In International Conference on Machine Learning, 2011.
Amir-massoud Farahmand, André M.S. Barreto, and Daniel N. Nikovski. Value-aware loss function for model-based reinforcement learning. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 1486-1494, April 2017.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In International Conference Artificial Intelligence and Statistics, 2010.
10

---

Published as a conference paper at ICLR 2020
Steffen Grunewalder, Guy Lever, Luca Baldassarre, Massi Pontil, and Arthur Gretton. Modelling transition dynamics in MDPs with RKHS embeddings. International Conference on Machine Learning. 2012.
Shixiang Gu, Timothy P. Lillicrap, lya Sutskever, and Sergey Levine. Continuous Deep Q-Learning with Model-based Acceleration. In International Conference on Machine Learning, pp. 2829- 2838, 2016.
Ha, David and Schmidhuber, Jürgen. Recurrent world models facilitate policy evolution. Advances in Neural Information Processing Systems, pp. -460-2462, 2018.
Steve Hanneke. Theory of disagreement-basee active learning. Foundations and Trends in Machine Learning, 7(2-3):131-309, 2014.
Hui Jiang. A new perspective on machine learning: How to do perfect supervised learning. CoRR:abs// SttR:aabb//991000466 2019.
Joshua Joseph, Alborz Geramifard, John W Roberts, Jonathan P How, and Nicholas Roy. Reinforce- ment learning with misspecified model classes. In Proceedings of IEEE International Conference on Robotics and Automation, pp. 939-946. IEEE, 2013.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Mitos, Blažej Osiński, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, Afroz Mohiuddin, Ryan Sepassi, George Tucker, and Henryk Michalewski. Model based reinforcement learning for atari. In International Conference Learning Representations, 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International
Conference on Learning Representations, 12 2014.
Weiwei Li and Emanuel Todorov. Iterative linear quadratic regulator design for nonlinear biolog- ical movement systems. In International Conference Informatics in Control, Automatin and Robotics, pp. 222 229, 2004.
Long-Ji Lin. Self-Improving Reactive Agents Based On Reinforcement Learning, Planning and Teaching. Machine Learning, 1992.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, and et al. Human-level control through deep reinforeement learning. Nature, 2015.
Andrew W. Moore and Christopher G. Atkeson. Prioritized sweeping: Reinforcement learning with less data and less time. Machine learning, pp. 103-130, 1993.
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. In NeurIPS, pp. 6118- 6128. Curran Associates, Inc., 2017.
Yangchen Pan, Muhammad Zaheer, Adam White, Andrew Patterson, and Martha White. Organizing experience: deeper look at replay mechanisms for sample-based planning in continuous state domains. In Proceedings of International Joint Conference on Artificial Intelligence, pp. 4794- 4800, 2018.
Yangchen Pan, Hengshuai Yao, Amir-massoud Farahmand, and Martha White. Hill climbing value estimates for search-control in dyna. In Proceedings of International Joint Conference on Artificial Intelligence, 2019.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized Experience Replay. In International Conference on Learning Representations, 2016.
Burr Settles. Active learning literature survey. Technical report, University of Wisconsin-Madison, 2010.
David Silver, Hado van Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Aulac-Arnold, David Reichert, Neil Rabinowitz, André M.S. Barreto, and Thomas Degris. The predictron: End-to-end learning and planning. In International Conference on Machine Learning, pp. 3191-3199, 2017.

---

Published as a conference paper at ICLR 2020
Steve Smale and Ding-Xuar Zhou. Shannon sampling and function reconstruction from point val- ues. Bulletin of the American Mathematical Society, 11:279-305. 2004.
Steve Smale and Ding-Xuat Zhou. Shannon sampling II: Connections to learning theory. Applied and Computational Harmonic Analysis, 19(3):285-302 2005.
Jonathan Sorg and Satinder Singh. Linear options. In Proceedings of the 9th International Confer- ence on Autonomous Agents and Multiagent Systems, pp. 31-38, 2010.
E.M. Stein and R. Shakarchi. Fourier Analysis: An Introduction. Princeton University Press, 2003.
R. Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Proceedings of the 12th International Conference on Neural Information Processing Systems. MIT Press, 1999.
Richard S. Sutton. Dyna, an integrated architecture for learning, planning, and reacting. SIGART Bulletin, 2(4):160-163, 1991a.
Richard S. Sutton. Integrated modeling and control based on reinforcement learning and dynamic programming. Advances in Neural Information Processing Systems, 1991b.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
Richard S. Sutton, Csaba Szepesvári, Alborz Geramifard, and Michael Bowling. Dyna-style plan- ning with linear function approximation and prioritized sweeping. In UAI, pp. 226-536,75 2008
Csaba Szepesvári. Algorithms for Reinforcement Learning. Morgan Claypool Publishers, 2010.
Erik Talvitie. Model regularization for stable sample rollouts. In Uncertainty in Artificial Intelli- gence, 2014.
Erik Talvitie. Self-Correcting Models for Model-Based Reinforcement Learning. In AAAI Confer- ence on Artificial Intelligence, 2017.
Y. Tassa, T. Erez, and E. Todorov. Synthesis and stabilization of complex behaviors through online trajectory optimization. International Conference on Intelligent Robots and Systems, 2012.
E. Todorov, T. Erez, and Y. Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033, 2012.
Harm van Seijen and Richard S. Sutton. A deeper look at planning as learning from replay. In International Conference on Machine Learning, pp. 2314-2322, 2015.
Christopher J. C. H. Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3):279-299) May 1992.
A.I. Zayed. Advances in Shannon's 's Sampling Theory. Taylor & Francis, 1993.
A APPENDIX
We provide calculations for Example I and Example 2 in Section A.1; theoretical proof of Theo- rem in Section A.2. Background of Dyna is reviewed in Section A.3 and additional discussions regarding search-control are provided in Section A.4. Additional experiments regarding separate cri- terion of hill climbing, and on continuous control problems are shown in Section A.5. Experimental details for reproducing empirical results are in Section A.6.
12

---

Published as a conference paper at ICLR 2020
A.1 CALCULATIONS FOR EXAMPLE I AND EXAMPLE 2
Example 1. For fsin defined in Eq. (1), calculate the integrals of squared first order derivative fain on high frequency region [-2,0] 0) and low frequency region [0, 2). respectively:
[ [in(())) dr = 64m², ['Vinlo)] de = n²
Proof. Taking derivative and integral,
[ (x)] de 64m² /" |cos (8Tx)) dx 64m²,
L (x)) de = x² S/¹ 1cos (TT)) dr = n².
Example 2. Let f [- + R be a band-limited real valued function defined as
f(x) do On cos (nz) + bn sin (nx),
where do, an bn E R. n2 1,2...., .2........... N are Fourier coefficients of frequency
a Then, 2
[ 18(x)²
dx Σ n (a + bb),
1 (f)) dx Σ nd (a + 6%.
Proof. Taking derivative of f,
N Σ
f'(x)
naa sin (ncr) + Σ [nbn cos (nx))
Taking square of f',
N
N
[(()))
Σ
Σ
pmma Orm sin (nar sin (mæ))
mama bm sin (var) cos (m.r)
1=1 m=1
n=1 m==
N
(mnam. bn sin (mzz) cos (ner)
Σ
Σ
bembyyb (nex) cos (mx))
mm
Taking integral,
N
N
((()))
do
(mman.a sin (ner sin (mer))dx
(nmaa bm sin (na)) cos (mæ)) dr
VI
N
mmnamb sin (max) cos (nx)]dr +
bm cos (nxx) cos (mz))dr
nu m=
am am 0 numb bm TT.
N
2 (n + b2),
1=1
where
del 11 if m,
8
0, otherwise.
13

---

Published as a conference paper at ICLR 2020
Using similar arguments, taking derivative of f'(x),
N
NV
(²(x)
= n an cos (nz)
+
Σ
n b, sin (nx))
n=1
Taking integral,
[+)) de Σ
n' (a bg)-
A.2 PROOF FOR THEOREM
Notations. For any vector norm ||. we mean l2 norm and we ignore the subscript unless clar- ification is needed. We use Frobenius norm || ||I for matrix. We use subscript yi denote the Ith element in vector y. Let Hy(v) be the Hessian matrix of f(y). We write H for short unless clarification needed, Let H1;: be the ith row of the Hessian matrix.
Proof description. We establish the connection between local gradient norm, Hessian norm and local frequency. To build such connection, we introduce a definition of f as shown below and we call it "local frequency distribution" of (z). f is a probability distribution over R", i.e., SEER= Tf (F(()dkk 1, and क (k) 2 0, Yk: IR Within an open subset of domain (an unit ball), this distribution characterizes the proportion of particular frequency component occupies. The proof can be described by three key steps:1) We use a local Fourier transform to express a function locally (i.e. within unit ball). we calculate the gradient/Hessian norm based this local Fourier transform; 3) we take integration over the unit ball of the gradient/Hessine norm to build the connection with the local frequency distribution πT and function energy.
Theorem 1. Given any function f 1=" I. for any frequency vector k E R", define its local Fourier transform of x E R",
I vEB().1) f(y) exp 12ii y k) dy.
f(k)
for local function around æ, ie.. y B(x,1) del by |1y - x|| < 1}. Assume the local function "energy" is finite,
[f(w)] dy [ < co, R".
(EB(1,1
R
Define "local frequency distribution" of f(x) as:
11 vkE
(k(k) del
JKn (1)
Then, Va E R", we have: 1) the first order connection:
/ JEB(E.)) [V dy = 4=2
( [ [f(1)1 dy
[/ Ty(k)) ||&|1 dl
2) the second order connection:
SySRLeD (H -167"
16
( ((())) dy [// TT(()) |B11 dl
Proof. 1) We first prove the first order connection. Consider the following function defined locally around s.
((v),
if E B(x, 1),
fv)
det
00 otherwise.
14

---

Published as a conference paper at ICLR 2020
By definition, the Fourier transform of fz is
f(k) [ vEB(o,1)
e 1 yn k dy
| (z(y) exp 122i y Th ki dy-
And the inverse Fourier transform [2( Vy E B(r, 1) is.
fz(8) f(k) exp (2xi - y k3 dk.
and then the gradient Vy E Bxx, 1) is
vs(y) = (v)
f(k) f2 y k (2Ti k) dk.
(8)
To calculate gradient norm, complex conjugate,
--2ii ( [ (k))) { 2Ti y TT3 (-2Ti : k') dk',
where
(((K) = J fa(v') exp 2 . v/ kk) dyj
the complex conjugate of ((k). Therefore,
|V/() = (V ())
[ [ [(K) {2ri T (k kD} (4=2kT R²) dkakk.
Taking integral of [V within the unit ball centered at
J VEB().1)
[V dy dy= f [v)l dy, by function definition
(10a)
Jen [ (()))()))) V/ exp {2ri y nn (k: - w)} dy) (4T2k" W) dkick'
(10b)
=fr
(Am2kT dlack!
(10c)
4T72 [ [[f(H)]22 |k|| dk.
(10d)
Recall the definition of local function "energy" around x,
[[(())]]dkk
(F(K), dk
(11a)
Rd
[ WER
[ exp {2 RT (v' f)} and dydy'
folw)
(11b)
WERn
(11c)
YER"
VER"
.f VER"
f2(ydd
(11d)
(y)ddy < co. (by definition of f=(v) and finite energy assumption)
vEB(E.1)
(11e)
15

---

Published as a conference paper at ICLR 2020
For (x, 1), the local gradient information is related to local energy and frequency distribution,
[ |.(())11.
11:11 Jan [l((k)) dk
|EBBUE.)
[V/(')] dy = 4
(12a)
J (k:)
1m
[ TT(K) [1]k))111
/ [[((b)]] 2
-5t²2
dhick
(12b)
P(o)dy) [/e Tz(k) |||]]² dk
(12c)
where the last equality follows by Jan [lf(k)))ddk Syen(a.1) Ply)dy which is established in the derivation (11).
2) Now we prove the second order connection. To show the second order connection, start from Eq. (8). Then the /th row of the Hessian matrix H1:: can be written as:
0V fV) T
H
dy:
where we use the notation avf(y) to denote the vector formed by taking partial derivative of each Ty element in the gradient vector (V) w.r.t. y1- Then,
@Vi(v)
/ f(k) exp {2mi y T (4 (e)))) dk:
Öy: R
where is standard basis vector where the Ith element is one. To calculate the norm of the complex conjugate again and follow the similar derivation done
sV.(w)
tor Hi.: in Eq. (9):
Oyn
Hr. (Hi., H..))
[ / f(k)) exp (2Ti- TT K)} (e6 ()(eT TT) dkdk' Jnn"
Note that the square of Frobenius of the Hessian matrix be written || Eis [l Ei=1 |1. Then,
|| Σn Hr.1112
Jeg [ f(k) (W') exp (2Ti yT (l: K1} 166777 Σ (e (eTK) k. dkdk
"
167 [ [ (k)) exp (2Ti y [k- (G) (KTR) k)
Taking the integration of || over y variable within a ball with center x and unit radius, we acquire:
[H( 1 / [1(()))11111))
Jy
/ ViEeee,
[ TT(A)) ||||
16
1f(v) dy
where the derivation process for the first equation a simple modification from the derivation (10) and the second equation follows the same derivation (12).
[]
16

---

Published as a conference paper at ICLR 2020
Algorithm 2 Generic Dyna Architecture: Tabular Setting
Initialize Q(s, a) and model M(s, a), V(s, (((s,))E E A while true do
observe s, take action a by e-greedy w.r.t Q(s,) ))
execute a, observe reward R and next state s' Q-learning update for Q(s. a)
update model M[s, a) (i.e. by counting)
store (8, a) into search-control queue
for i=1:d do
sample (3, a) from search-control queue
(). t ((3, (, â) // simulated transition
Q-learning update for Q(,, a) planning update
Discussion with Uncertainty Principle. We now provide intuitive interpretation of our the- orem from the well-known uncertainty principle. The Uncertainty Principle says that a function cannot be simultancously concentrated in both spatial and frequency space. That is, the more centrated a function is, the more spread out its Fourier transform must be, indicating that more high frequency terms are needed to express the function. For example, by uncertainty principle (Stein & Shakarchi, 2003), Vz E IR we have
U (u x)) [5)( dy [ [1f(())1)- -|A]1 di:
1
(13)
1672
measures the dispersion of the function around the point æ. Hence the smaller this term is, the more concentration of the function is on the specified domain. Plug into Eq. (5) and replace the function energy term by Fourier transform and cancel out the normalization term, we get:
Note that the first term
[ (y x²² (v)) dy
(y x)= ( ()) V
[
1
[v(()) dy
|V
dy 2 -
which means the more concentrated is locally around x, the larger the lower bound of the local gradient norm must be.
A.3 BACKGROUND IN DYNA
In this section, we provide the vanilla (tabular) Dyna (Sutton, 1991a; Sutton & Barto, 2018) in Algorithm 2, and Hill Climbing Dyna by Pan al. (2019) in Algorithm Dyna classic model- based reinforcement learning architecture. As described in Algorithm 2, at each time step, the real experience is used to directly improve policy/value estimates, and is also used to learn the environment dynamics model. During planning stage, simulated experiences learned model and are used to further improve the policy. The critical component in Dyna is the search-control mechanism, which decides what simulated experiences to during planning. This area relatively unexplored, though abundant literature is available regarding how to learn a model.
acquired from the
A.4 A DISCUSSION ON SEARCH-CONTRON DESIGN BASED ON HILLI CLIMBING
There are different ways to combine hill climbing strategies. Here are some unsuccessful trials. For example, climbing on direct combinations of (ss) (value function) and g(s) (frequency criterion), such as (ss) + g(s), or (s)g(s)), did not work well. The reasons are as following. First, such combination can lead to unpredictable gradient behaviour. It can alter the trajectory solely based on either g(s) or (s), and the effect is unclear. may lead to states with neither high value or high frequency. Last, and probably the most important, hill climbing on ((s) and on g(s) have fundamentally different insights. The former is based on the intuition that the value information should be propagated from the high value region to low value region; store states along the whole trajectory, including those in low value region. This is empirically verified by Pan et al. (2019). However, the latter is based the insight that the function value
result, it requires to
17

---

Published as a conference paper at ICLR 2020
Algorithm 3 HC-Dyna architecture
Bg: search-control queue, B: the experience replay buffer
m: number of states to fetch by search-control
b: the mini-batch size
while true do
Observe St, take action de (i.e. e-greedy w.r.t. action value function)
Observe 11+1, Te+1, add (st, de, 1, (r+11 to B
sample 8 from visited states, i.e. ER buffer B
// Hill climbing by gradient ascent while get less than m states do
V.V(s,, V(s) max, Qo(s, store 8 into search control queue B.
// Planning stage for d times do
// sample states from B, and pair them with on-policy actions, query the model to get next states and rewards
// mix simulated and real experiences into mini-batch and use it to update parameters
(i.e. DQN update)
t +++
in high frequency region is more difficult to approximate and needs more samples, while there is obvious reason propagate those information back to low frequency region. As a result, this approach does not emphasize on recording states throughout the whole hill climbing trajectory.
A.S ADDITIONAL EXPERIMENTS
In this section, we briefly study the effect of doing hill climbing on only gradient norm or Hessian norm. Then demonstrate that search-control strategy be also used for continuous control algorithms.
Hill climbing on only gradient norm Hessian norm. Throughout our paper, of g(s) = V [ to search states from high (local) frequency region of the value function. Besides the theoretical reason, there is a practical demand of such design. On value func- tion surface, regions which have low (or even zero) gradient magnitude may have high Hessian magnitude, and vice versa. Hence, it can help move along the gradient trajectory in case that one of the term vanished at some point. Such cases can be result of function approximation (smooth- ness/differentiabiltty,, or of the nature of the task, or both. In Fig. 6, we show the results of using only either gradient norm or Hessian norm. The reason we choose MountainCar and GridWorld (the same domain described by Pan et al. (2019)) that, the former has value function surface with lots of variations; while the latter's 's value function increases smoothly from the initial state to the goal state, which indicates small magnitude second-order derivative. Indeed, we empirically observe that the term V. Hx) frequently gives zero vector on Grild This explains the bad performance of Ooyna-HessNore in Fig. 6(b). contrast, Fig. 6(a) shows slightly better perfor- mance of Dyna-HessNorm and Vyna-GradNoma
the form
Notice that, an intuitive and more general form of g(x) can be g(s) = 7/ V. Vs)) [2 + 722 | H, (s)) [ P. at the cost that additional meta meta-parameters are introduced.
Continuous Control. In this section, we show a simple demonstration where our method is adapted to two continuous control tasks: Hopper-v2 and Walker2d-v2 from Mujoco (Todorov et al., 2012) by using a continuous Q learning algorithm called NAF (Normalized Advantage Function) (Gu et al., 2016). The algorithm parameterizes the action value function Q(s,a) (ss) - (a- - ( P(a μus)) where P is positive semi-definite matrix and hence the action with maximum value can be easily found: arg max, ((s. μu(s). Our search-control strat- egy naturally applics here by utilizing the value function Vss). From Fig. 7, one can see that our algorithm (DynaNAF-Frequenn Frequency)) finds better policy comparing with the model-free NAF.
18

---

Published as a conference paper at ICLR 2020
250
-250-
Sum
Sum
of rewards
of
per Episode (30runs)
per Episade (30runs)
Dyna-Frequency Dyna-GradNorm
-1750
Dyna-HessNorrm
-1750
-2000
2000
0.5
2.0
4.0
0.5
2.0 time steps
4.0
time steps
1e4
1e4
(a) plan steps MountainCar
(b) plan steps 10, GridWorld
Figure 6: Evaluation curves (sum of episodic reward v.s. environment time steps) of hill climbing on gradient norm ODya-GrraNNee and Hessian norm DDyna-HessNore on MountainCar and GridWorld with planning updates. results are averaged over random seeds.
500
1000
NAF
DynaNAF-Frequenlel
800
600
300
400
200
200
100
DynaNAF-Frequency
0
1
2
3
3
time
le5
time
le5
(a) Hopper-v2
(b) Walker2d-v2
Figure 7:
The learning curves showing sum rewards per episode as a function of environment time steps. We use 5 planning steps for both algorithm. The results averaged over 10 random seeds.
A.6 REPRODUCIBILITY DETAIL
All of implementations are based on tensorflow with version 1.13.0 (Abadi et al., 2015). For DQN update, we use Adam optimizer (Kingma & Ba, 2014). We use mini-batch size b = 32 except on the supervised learning experiment where use 128. For reinforcement learning experiment, we use buffer size 100k. All activation functions are tanh except the output layer of the Q-value linear. Except the output layer parameters which [-0.003,0.000 0.003]. all other parameters are initialized using Xavier initialization (Glorot & Bengio, 2010). For model learning, state-action pair with mini-batch size 128 and learning rate 0.0001.
initialized from uniform distribution
use 64 64 relu units neural network predict s' given
For the supervised learning experiment shown in Section 3, we use 16 16 tanh units neural net- work, with learning rate 0.001 for all algorithms. The learning curve is plotted by computing the testing error every 20 iterations. When generating Fig. 2, in order sample points according to p(x) [s)())) or p(x)) x (x)( we use 10, 000 even spaced points on the domain [-2, 2] and the probabilities are computed by normalization across the 10k points.
The experiment on MountainCar is based on the implementation from OpenAl (Brockman et al., 2016), we use 32 x 32 tanh layer, with target network moving rate 1000 and learning rate 0.001. Exploration noise is 0.1 without decaying. For all algorithms, we use warm up steps 5000 (i.e. random action is taken the first 5k time steps). Prioritized experience replay (PrioritizedER) is implemented the proportional version with tree data structure. We use prioritized ER without importance ratio but half mini-batch samples are uniformly sampled from the buffer as a strategy for bias correction. For Dyna- Value and Dyna-Frequency, use: gradient ascent step size (in
19

---

Published as a conference paper at ICLR 2020
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.8.5 0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
(a) frequeney-ban based search-control states
(b) value-based search-control states
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
6.0
0.2
0.4
0.6
0.8
1.0
0.0
1.0
(c) frequency-based ER states
(d) value-based ER states
Figure 8: The state distribution in the search-control queue and ER buffer at 50, 000 environment time step. The blue shadow indicates the hole area where the agent can go through the wall. The black box on the right top is the goal area.
scarch-control) 0.01, mixing rate 3 = 0.5 and m 20. i.e., at each environment time step we fetch 20 states by hill climbing. We fix p 0.5 across all experiments, hence the hill climbing rules (7a) and (7b) are selected with equal probability. We use natural projected gradient ascent for hill climbing as introduced by Pan et al. (2019).
For the experiment MazeGridWorld, each wall's width is 0.1 and each hole has height 0.1. The left-top point of the hole the first wall (counting from left to right) has coordinate (0.2, 0.5); the hole in the second wall has coordinate (0.4, 1.0) and the third one is 0.7, 0.2. Each action leads to 0.05 unit move perturbed by a Gaussian noise from (0, 0.01). On this domain, for both Dyna- Value and Dyma-Frrquency. all parameters that we use 64 x 64 tanh units for Q network, and number of search-control samples set as m 50, number of planning updates is 30. As supplement to the Section 5.2, also provide the state distribution from ER buffer in Figure 8. One can see that ER buffer has very different state distribution with search-control queue.
set the same with that used MountainCar except
A.7 ALGORITHMIC DETAILS
We provide the pseudo-code in Algorithm 4 with sufficient details to recreate our experimental results. The hill climbing rules we used is the same introduced by Pan et al. (2019). Define
V. max Q(,
then
9. V.g(s) v.( V. max Q), + (+) = v, (l IVV...11...
Note that we use a squared norm to ensure numerical stability when taking gradient. Then for value-based search-control, use
s + [S.Uull
S.V. Xx, X NO..
(14)
20

---

Published as a conference paper at ICLR 2020
and for frequency- based search-control,
st s +
|ل,9uع| E.g. + X,, X1 N(0,7
(15)
where Dg is empirical covariance matrix estimated from visited states, and we set 0.01, 0.01 across experiments. Notice that comparing with the previous work, we omitted the projec- tion step found is unnecessary in experiments.
Algorithm 4 Dyna architecture with Frequency- based search-control with additional details
Bg: search-contro queue, B: the experience replay buffer : A + S x I., the environment model number of search-control samples to fetch each step y: probability choosing value-based hill climbing rule (we set p = 0.5 for all experiments)
E 1]: mixing factor mini-batch, i.c. ,bb samples mini-bate are simulated from model
n: number of state variables, i.c. F"
empirically learned threshold as sample average of ||s411 -t s1l2//v
d: number of planning steps
Q, Q': current and target Q networks, respectively
b: the mini-batch size
update target network Q' every T updates to Q
+- is the time step
T2, <- 0 is the number of parameter updates
Gradient ascent hill climbing
With probability p, 1 p. choose hill climbing Eq. (14) Eq. (15) respectively; sample from B, if choose rule Eq. (14), or from B otherwise; set f 0, t while m do
update by executing the chosen hill climbing rule s of state space then: resample the initial state and hill climbing rule With probability
p. choose hill climbing rule Eq. (14) or Eq. (15) respectively; sample s from B, if choose Eq. (7), from B otherwise; set <- 8 continue
if ||s Vile/VR>> Eo then:
add to B,, + s, c+1
d planning updates; sample mini-batches for d times do // planning updates
sample 3b states from B, and pair them with on-policy actions, and query M get next states and rewards
sample b(1 3) transitions from an stack these with the simulated transitions use the mixed mini-batch for parameter (i.e. DQN) update
nr f- n1 +1 if mod(n = 0 then:
Q' + Q
++1+1
21


Reviews:
[{"review_id": "r1eEdLMyjH", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Disclaimer: \nThis is an emergency review that I got assigned on Nov 5th, so I unfortunately had only a few hours to assess the paper.\n\nSummary:\nThis paper proposes a new mechanism for “search control”, that is, choosing the planning-start-states from which to roll out the model, in the context of Dyna-style updates. The key idea is to favour updates to states where the the value functions changes a lot, because those need more information to become accurate.\nThe topic is very interesting, and not studied enough, the proposed method looks novel, and the experimental results look promising. However, the clarity of the paper is not great, the theoretical result (Theorem 1) seems to be incorrect, the narrative from Claude Shannon to Joseph Fourier to gradient norms to practical choices is somewhat confusing, the empirical results are not really conclusive, and despite a large appendix there are missing implementation details. I think this paper is currently one or two major revisions away from the acceptance threshold.\n\nComments:\n1. Theorem 1, equation (3): consider a constant function f(x) = K. Then its derivative is zero, so the left-hand side is zero, yet the right-hand side is the product of two strictly positive factors (each of them proportional to K^2), so how can the equation hold?\n2. Sine experiment: How can you reasonably do *linear* regression onto a sine function? What are your input features?\n3. Figure 2 is odd: panels (b) and (c) look very similar in how they bias the sampling toward the left side, yet the performance difference (a) is very stark, how come? Also, how can there be such a high contrast in (b)/(c) if 60% of all samples are chosen uniformly, as stated in the text?\n4. The paper has numerous grammatical mistakes, to the extent it becomes difficult to read. I know this can happen in deadline mode, but please revise the draft thoroughly (special call-out to the dozens of missing definite/indefinite articles and plural forms). Also, use “\\citep” where appropriate.\n5. The objective g as the sum of a gradient norm and a Hessian norm seems odd, as these terms have completely different scales, so usually one of them will dominate, can you explain and motivate this further, and compare empirically to the two terms in isolation?\n7. For the prioritizedER baseline, what variant and hyper-parameters are you using?\n8. Please describe “out of boundary” mentioned in Algorithm 1.\n9. Section 5.2 states that the “variance of the evaluation curve” is smaller, indicating robustness, yet Figure 3(a) appears to have high instability in the (early) learning curve?\n10. Section 5.2 states that Figure 5 should show that the bottleneck areas are sampled more densely, but that’s a dubious claim. Please quantify the claim or drop it.\n11. Figure 4(b) has oddly wide error-bars for DQN-Value, which looks suspiciously like a single failed run. Can you add a plot to the appendix with median/quantiles instead of mean/std statistics?\n\n\n--------------\nUpdate Nov 17: most of my concerns have been addressed, and I have thus increased my rating.\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJglemDstB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Summary:\nThis paper basically built upon [1]. The authors propose to do sampling in the high-frequency domain to increase the sample efficiency.  They first argue that the high-frequency part of the function is hard to approximate (i.e., needs more sample points) in section 3.1. They argue that the gradient and Hessian can be used to identify the high-frequency region. And then they propose to use g(x)=||gradient||+||Hessian || as the sampling metric as illustrated in Algorithm 1. To be noticed that, they actually hybrid the proposed metric (6) and the value-based metric (7, proposed in [1]) in their algorithm.\n\nStrength:\nCompared to [1], their experiment environment seems more complicated (MazeGridWorld vs. GridWorld). \nFigure 3 shows that their method converges faster than Dyna-Value.\nFigure 5 is very interesting. It shows that their method concentrates more on the important region of the function. \n\nWeakness:\nIn footnote 3: I don't see why such an extension is natural.\nIn theorem 1, why the radius of the local region has to be?\nTheorem1 only justifies the average (expectation) of gradient norm is related to the frequency. The proposed metric $g$, however, is evaluated on a single sample point. So I think if adding some perturbations to $s$ (and then take the average) when evaluating $g$ will be helpful.\nThe authors only evaluate their algorithm in one environment, MazeGridWorld. \nI would like to see the experiment results of using only (6) as the sampling rule. \nWhat kind of norm are you using? (||gradient||, ||hessian||)\nWhy $g$ is the combination of gradient norm and hessian norm? What will be the performance of using only gradient or hessian?\nFigure 4(b), DQN -> Dyna\n\nReference:\n[1] Hill Climbing on Value Estimates for Search-control in Dyna", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Byx_XzzJir", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes a new way to select states from which do do transitions in dyna algorithm (which trains policy from model experience as if it was a real experience). It proposes to look for states where frequency of value function as a function of a real valued state is large, because these are the states where the function is harder to approximate. The paper also shows that such frequency is large where the gradient of the function is large in magnitude which allows for finding such states in practice. In more detail, similar to previous algorithms, this algorithm keeps both an experience replay buffer as well as another buffer of states (search-control queue) and uses a hill climbing strategy to find states with both higher frequency and higher value. The paper tests the algorithm on toy domains - the mountain car and a maze with doors.\n\nThe idea of using the magnitude of the gradient as an exploration signal is not new - “go to places where agent learns more”. In this paper, such signal is not used as a reward but for finding states from which to do training updates. It is also nice that the paper provides a good relation (with explanation) between this signal and the frequency of the value function. The paper is clearly written. One drawback is that the main computations are only tractable in toy domains - it would be good if they discussed how to use this with general neural model with large state spaces (e.g. states obtained with an RNN).\n\nDetailed comments:\n- In the abstract it says “…searching high frequency region of value function”. At this point it is not clear what function we are considering - what is on the axes? - a time, state, value? (value on y axis and a real valued state on the x as it turns out later).\n- Same at line end-7 on page 2\n- End of section 2: and states with high value (as you do later).\n- A demonstration experiment: Why do you fit linear regression to a sin function? Why not at least one layer NN?\n- Page 5 top: You reason that Hessian learns faster - why not just squaring gradient norm?\n- Section 4: Hessian is intractable for general neural network unless you have a toy domain - does it work with just the gradient? This is an important point if this is to be scaled. May be you can also discuss how to compute the gradient of the norm of the gradient.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are unanimous in their evaluation of this paper, and I concur.
Decision: Accept (Poster)