Learning is an adaptation that allows individuals to respond to environmental stimuli in ways that improve their reproductive outcomes. The degree of sophistication in learning mechanisms potentially explains variation in behavioral responses. Here, we present a model of learning that is inspired by documented intra- and interspecific variation in the performance of a simultaneous two-choice task, the biological market task. The task presents a problem that cleaner fish often face in nature: choosing between two client types, one that is willing to wait for inspection and one that may leave if ignored. The cleaner's choice hence influences the future availability of clients (i.e., it influences food availability). We show that learning the preference that maximizes food intake requires subjects to represent in their memory different combinations of pairs of client types rather than just individual client types. In addition, subjects need to account for future consequences of actions, either by estimating expected long-term reward or by experiencing a client leaving as a penalty (negative reward). Finally, learning is influenced by the absolute and relative abundance of client types. Thus, cognitive mechanisms and ecological conditions jointly explain intra- and interspecific variation in the ability to learn the adaptive response.