A vast space of compact strategies for effective decisions

Abstract

Inference-based decision-making, which underlies a broad range of behavioral tasks, is typically studied using a small number of handcrafted models. We instead enumerate a complete ensemble of strategies that could be used to effectively, but not necessarily optimally, solve a dynamic foraging task. Each strategy is expressed as a behavioral "program" that uses a limited number of internal states to specify actions conditioned on past observations. We show that the ensemble of strategies is enormous-comprising a quarter million programs with up to five internal states-but can nevertheless be understood in terms of algorithmic "mutations" that alter the structure of individual programs. We devise embedding algorithms that reveal how mutations away from a Bayesian-like strategy can diversify behavior while preserving performance, and we construct a compositional description to link low-dimensional changes in algorithmic structure with high-dimensional changes in behavior. Together, this work provides an alternative approach for understanding individual variability in behavior across animals and tasks.

Fig. 1.. Constructing compact behavioral programs.

(A) Top: The space of strategies for solving a task can be large, with many strategies that achieve good enough performance. Bottom: Studying relationships between strategies could provide insight into behavioral variability across animals and tasks. (B) General task setup: An animal makes inferences about hidden properties of the environment to guide actions. (C) Specific task setup: An animal forages from two ports whose reward probabilities change over time. (D) The optimal unconstrained strategy consists of an optimal policy coupled to a Bayesian ideal observer. (E) We formulate a constrained strategy as a small program that uses a limited number of internal states to select actions based on past actions and observations. (F) Each program generates sequences of actions depending on the outcomes of past actions. (G) The optimal unconstrained strategy (D) can be translated into a small program by discretizing the belief update implemented by the ideal Bayesian observer and coupled to the optimal behavioral policy. Top: Optimal belief update. Middle: Belief values can be partitioned into discrete states (filled circles) labeled by the action they specify (blue versus green). The belief update specifies transitions between states, depending on whether a reward was received (solid versus dashed arrows). Bottom: States and transitions represented as a Bayesian program. (H) Top: A 30-state program approximates the Bayesian update in (G) and has two directions of integration that can be interpreted as increasing confidence about either option. Bottom: The two-state Bayesian program, win-stay, lose-go (WSLG), continues taking the same action upon winning (i.e., receiving a reward) and switches actions upon losing (i.e., not receiving a reward). (I) Example behavior produced by the 30-state Bayesian program in (H).

Fig. 2.. The space of behavioral programs is highly structured.

(A) There exist 268,536 unique programs with up to M = 5 internal states; these can be grouped according to performance (left) and structure (right). Note that the optimal Bayesian strategy, with M → ∞, is not included in this ensemble. (B) Structurally Bayesian programs have two clear directions of integration that can be interpreted as increasing confidence about a particular option (see Fig. 1H); in contrast, no matter how one orders the program states, structurally non-Bayesian programs do not have such clear integration or interpretation. (C) Decomposition of program space for increasingly large programs. As the maximum program size increases, structurally Bayesian programs comprise an exponentially small proportion of all good programs. (D) Depending on the underlying organization of the program space, changes in structure could lead to patchier or smoother changes in performance. (E) Sorting the set of two-state programs by performance reveals that each neighboring pair of programs is related by a single algorithmic mutation (top; colored arrows), defined as a relabeling of a single state or a relocation of a single transition (bottom). The “win-go, lose-stay” program (program C) suffers from the worst performance; it requires three mutations for this program to exceed chance performance and four mutations to match WSLG (program 0). (F) We designed a tree embedding algorithm to extract relationships between program structure and performance, shown for all programs with up to M = 4 states (note that program 5108 is not in this embedding; see fig. S5 for a full visualization up to M = 5 states). In this embedding, each node corresponds to a single program, each edge corresponds to a single mutation, and colors indicate performance. (G) An evolutionary algorithm discovers a large fraction of all good programs by searching a small fraction of the entire program space.

Fig. 3.. Behaviorally distinct programs emerge from a handful of key mutations.

(A) Structural mutations could have differing impact on behavior depending on whether they create behavioral diversity. (B) Example behavioral sequence expressed in terms of actions (“stay” and repeat an action versus “go” and select a different action) conditioned on past outcomes (“win” versus “lose”). (C) Some behavioral sequences are unique to each program (top rows), and some are shared (bottom rows; circle sizes denote the relative probability of observing sequences within each category, computed across all sequences produced by the set of three programs). Program 7 is distinguishable because many of its most probable sequences are not shared. (D) We measure how easily each program can be distinguished among the ensembles of good programs and structurally Bayesian programs (M ≤ 5), and we use thresholds to select globally distinguishable and behaviorally non-Bayesian programs (colored points; Materials and Methods). We use 262 connection programs to embed good programs in a single connected subtree; 27 of these exhibit lower-than-random performance (low-performing; Materials and Methods). (E) A behavioral tree embedding relates program structure and behavior, shown for all programs in (D). As in Fig. 2D, nodes and edges correspond to programs and mutations, respectively. Node sizes denote global distinguishability; colors denote groupings in (D). The confusion matrix inset clusters globally distinguishable programs into nine behavioral subgroups; for visualization, the heatmap saturates at one SD above the mean. By traversing from the root node (WSLG; program 0) toward leaf nodes, a small number of key mutations can generate behavioral diversity, indicated by colored points (e.g., a single key mutation to program 9 alters the behavior of its descendant, program 24). Programs can also undergo sloppy mutations that do not substantially change behavior (e.g., several sloppy mutations to program 5 preserve the behavior of its descendant, program 7403).

Fig. 4.. Functional motifs combine to generate diverse behavior.

(A) We sought an interpretable functional logic to capture the high-dimensional distribution of sequence probabilities (top) using a small number of functional elements (bottom). (B) For each program, we extract a minimal set of behavioral subsequences, or functional motifs, that capture a majority of its behavioral sequences (Materials and Methods). Each motif can be visualized by traversing an action-outcome path through a program and must form a stable loop when repeated in succession (red box). (C) In (D) to (I), we use motifs to study behavioral features that are inherited along different lineages of the behavioral tree in Fig. 3E. (D) Distribution of motifs across different behavioral subgroups. Inset shows the rate at which new non-Bayesian motifs are generated by structurally non-Bayesian programs. (E) Top five non-Bayesian motifs shared by a majority of programs within each behavioral subgroup (note that subgroup 7 only expresses four non-Bayesian motifs). See fig. S11 for full characterization. (F) A key mutation to program 9 creates new non-Bayesian motifs within program 24 (starred bars; e.g., lw) that distinguish the descendants of programs 9 and 24 (left and right histograms, respectively). (G) Example program lineage. Motif LWll is inherited by the descendants of program 9 through sloppy mutations. Program 24 inherits this motif and creates a new motif, lw, via a key mutation; this is inherited by its descendants through sloppy mutations. (H and I) Two examples of functional convergence between a descendant of program 9 and a program on a distant lineage (C), where structurally distinct programs use the same (H) or different (I) combinations of motifs to generate the same sequences. (J) Good performance can be achieved through different behavior, which can be generated by different combinations of functional motifs that are themselves expressed by many structurally distinct programs.