Learning is a fundamental mechanism in the behavior of animals. Theorists have long proposed that learning is an adaptation to environmental change, but change itself can present a logical paradox in that change can select both for and against learning. One way to resolve this paradox is through separating change into different components, such as the reliability of stimuli that can be used as cues for behavior, and the certainty with which those cues predict the best behavior to employ. Simple models using these components of change can be successfully applied through experimental evolution to directly test hypotheses of when learning and innate preference will each be favored evolutionarily, as well as when prepared learning will evolve. Costs of learning and, in particular, economic costs such as opportunity costs, should influence when learning will be favored. Although experimental evolution of learning can be difficult in practice, the benefits of the approach far outweigh difficulties. Future studies might approach the role of opportunity costs and how reliability and certainty fully interact to influence the evolution of learning.