Service migration in mobile edge computing is a promising approach to improving the quality of service (QoS) for mobile users and reducing the network operational cost for service providers as well. However, these benefits are not free, coming at costs of bulk-data transfer, and likely service disruption, which could consequently increase the overall service costs. To gain the benefits of service migration while minimizing its cost across the edge nodes, in this paper, we leverage reinforcement learning (RL) method to design a cost-effective framework, called Mig-RL, for the service migration with a reduction of total service costs as a goal in a mobile edge environment. The Mig-RL leverages the infrastructure of edge network and deploys a migration agent through Q-learning to learn the optimal policy with respect to the service migration status. We distinguish the Mig-RL from other existing works in several major aspects. First, we fully exploit the nature of this problem in a modest migration space, which allows us to constrain the number of service replicas whereby a defined state–action space could be effectively handled, as opposed to those methods that need to always approximate a huge state–action space for policy optimality. Second, we advocate a migration policy-base as a cache to save the learning process by retrieving the most effective policy whenever a similar migration pattern is encountered as time goes on. Finally, by exploiting the idea of software defined network, we also investigate the efficient implementation of Mig-RL in mobile edge network. Experimental results based on some real and synthesized access sequences show that Mig-RL, compared with the selected existing algorithms, can substantially minimize the service costs, and in the meantime, efficiently improve the QoS by adapting to the changes of mobile access patterns.