Recently, network virtualization is considered as a promising solution for the future Internet which can help to overcome the resistance of the current Internet to fundamental changes. The problem of embedding Virtual Networks (VN) in a Substrate Network (SN) is the main resource allocation challenge in network virtualization. The major challenge of the Virtual Network Embedding (VNE) problem lies in the contradiction between making online embedding decisions and pursuing a long-term objective. Most previous works resort to balancing the SN workload with various methods to deal with this contradiction. Rather than passive balancing, we try to overcome it by learning actively and making online decisions based on previous experiences. In this article, we model the VNE problem as Markov Decision Process (MDP) and develop a neural network to approximate the value function of VNE states. Further, a VNE algorithm based on Temporal-Difference Learning (one kind of Reinforcement Learning methods), named VNE-TD, is proposed. In VNE-TD, multiple embedding candidates of node-mapping are generated probabilistically, and TD Learning is involved to evaluate the long-run potential of each candidate. Extensive simulation results show that VNE-TD outperforms previous algorithms significantly in terms of both block ratio and revenue.