To make good decisions, animals and humans learn from the consequences of their earlier choices to guide later decisions. For instance, as toddlers we learn to say “please”, later, we learn how to behave at cocktail parties. Chimpanzees learn how to use a stick for termites. New-Caledonian Crows learn how to bend a wire for a food reward. Honeybees learn at what time of day they have to visit which flower patch. Such learning situations often consist of an early, exploratory phase and a later phase in which the behavior is reliably produced to exploit a resource. Psychologically speaking, animals have to transition from producing spontaneous, exploratory actions, to efficient, habitual responding. Using the genetic tools available in the fruit fly Drosophila melanogaster, we discovered that such complex tasks are accomplished by processing them with two separate, but interacting learning systems. The first, dominant system stores any relationships between stimuli in our environment. The second, anatomically and genetically distinct system is subordinate and directly modifies behavioral circuits. Their hierarchical interactions ensure that the information each animal acquires about its environment remains flexible for use in different circumstances (generalization). Prolonged exposure to a given situation reduces this flexibility in favor of a more efficient, stereotyped behavior (habit formation). In Drosophila, the molecular mechanisms of these two learning systems are starting to unravel. A prominent neuropil, the mushroom-bodies are mediating some of the interactions between these systems and regulate the balance between flexible exploration and efficient exploitation.