Cloud of Things (CoT) is a significant paradigm for bridging cloud resource and mobile terminals. Mobile edge computing (MEC) is a supporting architecture for CoT. The objectives of this paper are to describe and evaluate a method to handle the computation offloading problem during user mobility which minimizes the offloading failure rate in heterogeneous network. Furthermore, users’ mobility and their choices for offloading lead to the everchanging condition of wireless network and opportunistic resource available. By modeling such dynamic mobile edge environment, quantizing the user cost, failure penalty and diversified QoS requirements, computation offloading problem is converted into an online decision-making problem in a stochastic process. We divide the decision-making into two phases: offloading planning phase and offloading running phase. In both phases the learning agent can continuously improve the control policy. We also conduct a failure recovery policy to tackle different types of failure and is included in the decision-making process. The numerical results show that the proposed online learning offloading method for mobile users can derive the optimal offloading scheme compared with the baseline algorithms.