That is a very interesting question, and it depends how deep you want to take the inquiry as to what sort of answer you get.
Oliver Caspari gave a good and valid answer at one level.
If you go back to the beginning, evolution is the differential survival of the variants of something that can replicate with some degree of fidelity, in some set of contexts.
It seems very probable that the evolution of life really got under way with RNA molecules, then later DNA got added to the mix.
Since then it has been operating at multiple different levels simultaneously.
So it has the idea of the generation of variants, with some degree of randomness, and differential survival in different contexts.
Whenever there is sufficient threat from external factors that individual replicators can benefit more from cooperating against the external threats than competing with each other, then new levels of complexity can emerge, and every new level of complexity requires sets of attendant strategies to prevent being overwhelmed by cheating strategies. So evolution rapidly becomes a very complex strategic ecosystem at every level.
As modern human beings we seem to embody about 20 levels of such cooperative complexity. Thus in our case it is much more accurate to say that evolution is essentially about cooperation, rather than about competition, as the role of cooperative systems vastly outweighs the role of competitive systems in our survival both as individuals and as groups.
So back to the learning evolution question more directly.
What is learning?
It could be said to be the generation of pattern capable of being replicated, and the testing of that pattern in some context (either in our internal mental models of reality, or in action in reality itself), and a modification of the likely frequency of that pattern being expressed again (we either reinforce it, or we dampen it down).
So there is a sense in which learning can be thought of as high speed evolution of mimetic entities in some mix of intellectual and physical environments.
The more abstractly one defines it, the more recursive the notion becomes.
And evolution has been dealing with variations of “the halting problem” for a very long time, so we all have different sorts of mechanisms that prevent us from eternally chasing our intellectual “tails” down some recursive loop (in some people those mechanisms are so well developed that even a single loop is unlikely, in other people hunger and sleep deprivation will eventually drag them back some hours or days later).
So when one looks very closely at evolution, and at the factors that influence both the frequency and the cause of variation, then it becomes a very interesting picture indeed.
There is always some optimal rate of variation, that is always a balance between sufficient fidelity to maintain the levels of complexity already present, and sufficient novelty to cope with the variations in reality that inevitably happen from time to time. And that can get very complex with both directed and random sources of variation in different mixes in different contexts. And in this context I find something that emerged from database theory about a decade ago very interesting, that for a fully loaded processor, the most efficient possible search is the fully random search. And that throws up all sort of secondary issues as to how, with all our many levels of biases, we might approximate randomness. And this should give you some idea as to how complex it can get.
If you dig deep enough into everything about us, it all seems to come back to the differential survival of variants in some level of context; and there does not appear to be any end to the number of levels simultaneously possible.
And we all need to survive – every level.
Learning appears to be high level evolution; and evolution always embodies levels of complexity before any of the systems become conscious of such embodiment (there is no logical alternative – we are the result of such systems, not their cause, even as, with diligent practice, we become cause in the matter of our own form, at least to the degree that we do).