Model-based reinforcement learning has been empirically demonstrated as a successful strategy to improve sample efficiency. Particularly, Dyna architecture, as an elegant model-based architecture integrating learning and planning, 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 to improve learning efficiency. In this work, we propose a simple and novel search-control strategy by searching high frequency region on 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 in high frequency region 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 norm, 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. 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 & Schmidhuber, 2018; Kaiser et al., 2019) . 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 2 in Appendix A.3). At each time step, a Dyna agent uses the real experience to learn a model and to perform model-free policy update, 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. A crucial aspect of the Dyna architecture is the search-control mechanism. It 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 sample efficiency. A simple approach to searchcontrol is to sample visited states or state-action pairs, i.e., use the initial state-action pairs stored in the ER buffer as 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 a deterministic environment, and assume that we have the exact model. If we simply sample visited state-action pairs for searchcontrol, the next-state and reward would be the same as those in the ER buffer. In practice, we have 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 simulated transitions are updated based on 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 et 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 searchcontrol 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 regions of the state space where the value function is more difficult to estimate. In order to quantify the difficulty of estimation, we borrow a crucial idea from the signal processing literature: the Shannon sampling theorem, which establishes the connection between a signal's bandwidth and the number of samples required for its reconstruction. A signal with higher frequency terms requires more samples for accurate reconstruction (Shannon sampling theorem has been studied in learning theory too, e.g., by Smale & Zhou 2004; 2005; Jiang 2019) . A parallel of this idea in the learning setting is the heuristic that we would like to have more samples from regions of the state space where the value function has higher local frequency. We establish a connection between a function's local frequency and its gradient and Hessian norm. In order to sample from those regions, we use the hill climbing approach of Pan et al. (2019) . These allow us to propose a search-control mechanism that focuses on sampling from regions where learning the value function is likely to be more difficult. In this paper, 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). We observe that providing more samples in the high frequency region of a function can improve the efficiency of learning. We then propose a method to locally measure the frequency of a point in a function's domain and provide a theoretical justification for our method (Theorem 1 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 on benchmark and challenging domains to illustrate the properties and utilities of our method (Section 5). We motivated and studied a new category of methods for search-control by considering the approximation difficulty of a function. We provided a method for identifying the high frequency regions of a function, and justified it theoretically. We conducted experiments to illustrate our theory. We incorporated the proposed method into the Dyna architecture and empirically investigated its benefits. The method achieved competitive learning performances on a difficult domain. There are several promising future research directions. First, it is worth exploring the combination of different search-control strategies. Second, exploring the use of active learning methods (Settles, 2010; Hanneke, 2014) , which try to learn a function with as few samples as possible, to design search-control mechanism in MBRL algorithms might be a fruitful direction. Proof. Taking derivative and integral, Example 2. Let f : [−π, π] → R be a real valued function. We have a n , b n ∈ R, n = 1, 2, . . . are Fourier coefficients of frequency n 2π , defined as Proof. The Fourier series of f (x) is where a 0 Taking square of f , Using similar arguments, taking derivative of f (x),
Acquire states from high frequency region for search-control in Dyna. The authors propose to do sampling in the high-frequency domain to increase the sample efficiency This paper proposes a new way to select states from which do do transitions in dyna algorithm.