A key component for many reinforcement learning agents is to learn a value function, either for policy evaluation or control. Many of the algorithms for learning values, however, are designed for linear function approximation---with a fixed basis or fixed representation. Though there have been a few sound extensions to nonlinear function approximation, such as nonlinear gradient temporal difference learning, these methods have largely not been adopted, eschewed in favour of simpler but not sound methods like temporal difference learning and Q-learning. In this work, we provide a two-timescale network (TTN) architecture that enables linear methods to be used to learn values, with a nonlinear representation learned at a slower timescale. The approach facilitates the use of algorithms developed for the linear setting, such as data-efficient least-squares methods, eligibility traces and the myriad of recently developed linear policy evaluation algorithms, to provide nonlinear value estimates. We prove convergence for TTNs, with particular care given to ensure convergence of the fast linear component under potentially dependent features provided by the learned representation. We empirically demonstrate the benefits of TTNs, compared to other nonlinear value function approximation algorithms, both for policy evaluation and control.     Value function approximation-estimating the expected returns from states for a policy-is heavily reliant on the quality of the representation of state. One strategy has been to design a basis-such as radial basis functions (Sutton and Barto, 1998) or a Fourier basis BID17 )-for use with a linear function approximator and temporal difference (TD) learning (Sutton, 1988) . For low-dimensional observation vectors, this approach has been effective, but can be onerous to extend to high-dimensional observations, potentially requiring significant domain expertise. Another strategy has been to learn the representation, such as with basis adaptation or neural networks. Though there is still the need to specify the parametric form, learning these representations alleviates the burden of expert specification. Further, it is more feasible to scale to high-dimensional observations, such as images, with neural networks (Mnih et al., 2015; BID16 . Learning representations necessitates algorithms for nonlinear function approximation.Despite the deficiencies in specification for fixed bases, linear function approximation for estimating value functions has several benefits over nonlinear estimators. They enable least-squares methods, which can be much more data-efficient for policy evaluation BID5 Szepesvari, 2010; van Seijen and Sutton, 2015) , as well as robust to meta-parameters (Pan et al., 2017) . Linear algorithms can also make use of eligibility traces, which can significantly speed learning (Sutton, 1988; BID9 White and White, 2016 ), but have not been able to be extended to nonlinear value function approximation. Additionally, there have been a variety of algorithms derived for the linear setting, both for on-policy and off-policy learning (Sutton et al., 2009; BID23 van Seijen and Sutton, 2014; van Hasselt et al., 2014; Mahadevan et al., 2014; Sutton et al., 2016; Mahmood et al., 2017) . These linear methods have also been well-explored theoretically (Tsitsiklis and Van Roy, 1997; BID23 Mahmood and Sutton, 2015; Yu, 2015) and empirically BID9 White and White, 2016) , with some insights into improvements from gradient methods (Sutton et al., 2009 ), true-online traces (van Seijen and Sutton, 2014) and emphatic weightings (Sutton et al., 2016) . These algorithms are easy to implement, with relatively simple objectives. Objectives for nonlinear value function approximation, on the other hand, can be quite complex (Maei et al., 2009) , resulting in more complex algorithms (Menache et al., 2005; BID10 BID2 or requiring a primal-dual formulation as has been done for control BID8 .In this work, we pursue a simple strategy to take advantage of the benefits of linear methods, while still learning the representation. The main idea is to run two learning processes in parallel: the first learns nonlinear features using a surrogate loss and the second estimates the value function as a linear function of those features. We show that these Two-timescale Networks (TTNs) converge, because the features change on a sufficiently slow scale, so that they are effectively fixed for the fast linear value function estimator. Similar ideas have previously been explored for basis adaptation, but without this key aspect of TTNs-namely the separation of the loss for the representation and value function. This separation is critical because it enables simpler objectives-for which the gradient can be easily sampled-to drive the representation, but still enables use of the mean squared projected Bellman error (MSPBE)-on which all the above linear algorithms are based. This separation avoids the complexity of the nonlinear MSPBE, but maintains the useful properties of the (linear) MSPBE. A variety of basis adaptation approaches have used a two-timescale approach, but with the same objective for the representation and the values (Menache et al., 2005; BID10 BID2 . Yu and Bertsekas ( 2009) provided algorithms for basis adaptation using other losses, such as Bellman error using Monte carlo samples, taking derivatives through fixed point solutions for the value function. BID21 periodically compute a closed form least-squares solution for the last layer of neural network, with a Bayesian update to prevent too much change. Because these methods did not separate the value learn and basis adaptation, the resulting algorithms are more complex. The strategy of using two different heads-one to drive the representation and one to learn the values-has yet to be systematically explored.We show that TTNs are a promising direction for nonlinear function approximation, allowing us to leverage linear algorithms while retaining the flexibility of nonlinear function approximators. We first discuss a variety of possible surrogate losses, and their potential for learning a useful representation. We then show that TTNs converge , despite the fact that a linear algorithm is used with a changing representation. This proof is similar to previous convergence proofs for policy evaluation, but with a relaxation on the requirement that features be independent, which is unlikely for learned features. We then show empirically that TTNs are effective compared to other nonlinear value function approximations and that they can exploit several benefits of linear value approximations algorithms. In particular, for both low-dimensional and high-dimensional (image-based) observations, we show (a) the utility of least-squares (or batch ) methods, (b) advantages from eligibility traces and (c) gains from being able to select amongst different linear policy evaluation algorithms. We demonstrate that TTNs can be effective for control with neural networks, enabling use of fitted Q-iteration within TTNs as an alternative to target networks. In this work, we proposed Two-timescale Networks as a new strategy for policy evaluation with nonlinear function approximation. As opposed to many other algorithms derived for nonlinear value function approximation, TTNs are intentionally designed to be simple to promote ease-of-use. The algorithm combines a slow learning process for adapting features and a fast process for learning a linear value function, both of which are straightforward to train. By leveraging these two timescales, we are able to prove convergence guarantees for a broad class of choices for both the fast and slow learning components. We highlighted several cases where the decoupled architecture in TTNs can improve learning, particularly enabling the use of linear methods-which facilitates use of least-squares methods and eligibility traces.This work has only begun the investigation into which combinations for surrogate losses and linear value function approximation algorithms are most effective. We provided some evidence that, when using stochastic approximation algorithms rather than least-squares algorithms, the addition of traces can have a significant effect within TTNs. This contrasts nonlinear TD, where traces were not effective. The ability to use traces is potentially one of the most exciting outcomes for TTNs, since traces have been so effective for linear methods. More generally, TTNs provide the opportunity to investigate the utility of the many linear value function algorithms, in more complex domains with learned representations. For example, emphatic algorithms have improved asymptotic properties (Sutton et al., 2016) , but to the best of our knowledge, have not been used with neural networks.Another promising direction for TTNs is for off-policy learning, where many value functions are learned in parallel. Off-policy learning can suffer from variance due to large magnitude corrections (importance sampling ratios). With a large collection of value functions, it is more likely that some of them will cause large updates, potentially destabilizing learning in the network if trained in an end-to-end fashion. TTNs would not suffer from this problem, because a different objective can be used to drive learning in the network. We provide some preliminary experiments in the appendix supporting this hypothesis (Appendix C.7). θ,w ← GradientDescent on L slow using sample (s, r, s ) DISPLAYFORM0 w ← Update on L value using sample (s, r, s )8: DISPLAYFORM1 end while 10:return learned parameters w, θ,w 11: end procedure B CONVERGENCE PROOF OF TWO-TIMESCALE NETWORKS B.1 DEFINITIONS & NOTATIONS -Let R + denote the set of non-negative real numbers, N = {0, 1, 2, . . . } and · denote the Euclidean norm or any equivalent norm. DISPLAYFORM2 3. h is upper-semicontinuous, i.e., if {x n } n∈N → x and {y n } n∈N → y, where x n ∈ R d , y n ∈ h(x n ), ∀n ∈ N, then y ∈ h(x).-For x 1 , x 2 ∈ R d and D ∈ R k×k a diagonal matrix, we define the inner-product < x 1 , x 2 > D x 1 Dx 2 . We also define the semi-norm DISPLAYFORM3 D . If all the diagonal elements of D are strictly positive, then · D is a norm.-For any set X, letX denote the interior of X and ∂X denote the boundary of X. -For brevity, letθ = (θ,w) and Φθ be the feature matrix corresponding to the feature parameterθ, i.e. DISPLAYFORM4 where x θ (s) is the row-vector corresponding to state s. Further, define the |S| × |S|-matrix P π as follows: P π s,s a∈A π(s, a)P (s, a, s ), s, s ∈ S.-Also, recall that DISPLAYFORM5 is Frechet differentiable at x ∈ U if there exists a bounded linear operator Γ x : R d1 → R d2 such that the limit DISPLAYFORM6 exists and is equal to Γ x (y). We say Γ is Frechet differentiable if Frechet derivative of Γ exists at every point in its domain.
We propose an architecture for learning value functions which allows the use of any linear policy evaluation algorithm in tandem with nonlinear feature learning. The paper proposes a two-timescale framework for learning the value function and a state representation altogether with nonlinear approximators. This paper proposes Two-Timescale Networks (TTNs) and prove the convergence of this method using methods from two time-scale stochastic approximation.  This paper presents a Two-Timescale Network (TTN) that enables linear methods to be used to learn values. 