AbstractIn Network Virtualization Environments, the capability of operators to allocate resources in the Substrate Network (SN) to support Virtual Networks (VNs) in an optimal manner is known as Virtual Network Embedding (VNE). In the same context, online VN migration is the process meant to reallocate components of a VN, or even an entire VN among elements of the SN in real time and seamlessly to end‐users. Online VNE without VN migration may lead to either over‐ or under‐utilization of the SN resources. However, VN migration is challenging due to its computational cost and the service disruption inherent to VN components reallocation. Online VN migration can reduce migration costs insofar it is triggered proactively, not reactively, at critical times, avoiding the negative effects of both under‐ and over‐triggering. This paper presents a novel online cost‐efficient mechanism that self‐adaptively learns the exact moments when triggering VN migration is likely to be profitable in the long term. We propose a novel self‐adaptive mechanism based on Reinforcement Learning that determines the right trigger online VN migration times, leading to the minimization of migration costs while simultaneously considering the online VNE acceptance ratio.