Typical analysis of content caching algorithms using the metric of hit probability under a stationary request process does not account for performance loss under a variable request arrival process. In this work, we consider adaptability of caching algorithms from two perspectives: (a) the accuracy of learning a fixed popularity distribution; and (b) the speed of learning items’ popularity. In order to attain this goal, we first determine the stationary distributions of several popular caching algorithms. We compute the distance between the stationary distributions of each algorithm with that of an algorithm that has knowledge of the true popularity ranking. We then characterize the mixing time of each algorithm, i.e., the time needed to attain the stationary distribution, which we use as a measure of learning efficiency. We merge both results to obtain the “learning error” representing both how quickly and how accurately an algorithm learns the optimal caching distribution. Motivated by our analysis, we pro- pose a novel hybrid algorithm, Adaptive-LRU (A-LRU) that learns both faster and better the changes in the popularity. We show numerically that it outperforms all other candidate algorithms when confronted with a dynamically changing synthetic request process, as well by using real world traces.