In reinforcement learning, $\epsilon$-greedy exploration and additive Gaussian noise are standard techniques for visiting unknown regions of the state space. Especially when there is a change in the environment, the required amount of exploration can vary. We consider the problem of changing reward or dynamics functions and the resulting relearning of previously optimal policies. By defining the magnitude of change and exploration in Wasserstein distances, we show that there are direct relationships between them. For specific goal-reaching tasks in grid world environments, we show that the amount of necessary exploration to quickly rediscover the new goal is a monotonic function of the magnitude of change. We further provide empirical evidence that this monotonicity carries over to tabular and deep reinforcement learning settings, where exploration is optimized with respect to cumulative return.