Exploration versus exploitation in space, mind, and society

Abstract

Search is a ubiquitous property of life. Although diverse domains have worked on search problems largely in isolation, recent trends across disciplines indicate that the formal properties of these problems share similar structures and, often, similar solutions. Moreover, internal search (e.g., memory search) shows similar characteristics to external search (e.g., spatial foraging), including shared neural mechanisms consistent with a common evolutionary origin across species. Search problems and their solutions also scale from individuals to societies, underlying and constraining problem solving, memory, information search, and scientific and cultural innovation. In summary, search represents a core feature of cognition, with a vast influence on its evolution and processes across contexts and requiring input from multiple domains to understand its implications and scope.

Figure 1

Local exploration in human visual search. In visual search, people look for specific letter targets; for example, Fs in an array of letter distractors. The local exploitation step is the act of recognizing a letter and determining whether it is your target. The local exploration step is the act of selecting the next letter (accomplished at a rate of about 20–40 letters/s). All else being equal, visual attention is drawn to salient items in the field (A). How then are we to avoid perseverating on one incorrect but vivid letter? One answer (B) is to rely on the phenomenon of ‘inhibition of return’ (IOR) [94]. If one attends or fixates on an item and then deploys one’s gaze or attention away from that item, it becomes harder to bring the gaze or attention back to the original item than to move it elsewhere. It was originally believed that IOR would permit attention to sample the display without replacement. Unfortunately, further research found that visual search was not markedly impaired when IOR was blocked and observers had to sample with replacement. A more moderate view might hold that IOR serves to bias exploration toward new items (C) even if it does not absolutely prevent return to a rejected item. However, given enough time, observers can adopt strategies that allow them to prevent perseveration [95]. Thus, for example, one might ‘read’ a display from side to side and top to bottom. This more controlled, prospective strategy (D) would avoid sampling with replacement but would slow the rate with which items can be processed. In some cases, a more chaotic strategy will get you to the target more quickly [96].

Figure 2

Priming from external to internal search. (A) People initially searched for hidden targets (invisible to the participants, but shown in black) in environments with either clustered or diffuse resource distributions. The lower two panels show typical foraging patterns in the two environments. Following this period of foraging in external space, people’s internal search behavior was quantified in a lexical search task. In the lexical search task, participants were asked to find 30 words across a series of letter sets, with multiple words possible per letter set. (B) A network representation of search in one letter set where participants found multiple words in the letter set NSBDOE. Nodes represent solutions and links between nodes represent transitions between solutions. Node size is proportional to the number of participants who provided that solution. Link thickness is proportional to the number of participants who made that transition. Bigram similarity between previous solutions and the original letter set shows a clear tendency to produce solutions that are more like the previous solution, N – 1, than like solutions two items back, N – 2, or the letter set. Priming is shown in panel (C), with individuals in the clustered condition staying longer in letter sets (post-test–pretest time) than individuals in the diffuse condition. Reproduced from [33].

Figure 3

Collective search allows individuals to track environmental gradients that occur at long length scales relative to the size of individuals, as well as to track gradients that they cannot individually detect. (A) The positions of 30 fish are shown as they negotiate, collectively, a moving light field toward the preferred darker regions. The snapshots are 2 s apart, with time progressing downward. (B) Performance, as measured by the time-averaged darkness level at fish locations, increases with group size. Experiments (points connected by dotted line) and simulations (red line) show this to be a function of individual fish simply manipulating their speed (moving slower in darker regions) while maintaining connectivity via locally mediated social interactions. Thus, counter to the conventional view of the ‘wisdom of crowds’, in which individuals pool imperfect estimates [120], here detection of the local light gradient is absent at the individual level (individuals employ only a scalar measure of the light intensity at their present location), yet exploration and exploitation emerge as a dynamic property of the collective. Reproduced from [74].

Figure 4

Examples of cognitive approaches to the exploration–exploitation trade-off, as discussed in the text.