We study the robust transient and quickest change detection problems with unknown post-change distributions under finite alphabets. When the distribution after the change point is unknown, the change in the distribution of observations may occur in multiple ways without much structure on the observations, whereas, before the change point, a false alarm is highly structured, following a particular sample path with respect to the distribution of observations and the detection scheme. We first characterize these likely events for the deviation and propose a method to test the empirical distribution, relative to the most likely way for it to occur as an outlier. We show performance guarantees and prove asymptotic optimality for a robust quickest change detection problem up to a multiplicative constant before benchmarking our method with the finite moving average (FMA) method, generalized likelihood ratio test (GLRT) and M-statistic kernel (MSK) change point detection method under 4 different performance criteria including the run time complexity. Finally, we apply our method on economic market indicators and climate data. Our method successfully captures the regime shifts during times of historical significance for the markets and identifies the current climate change phenomenon to be a highly likely regime shift rather than a random event.