An Efficient Search for Novel Behavioral Strategies in a Vast Program Space
Tzuhsuan Ma, Ann Hermundstad, HHMI Janelia Research Campus, United States
Posters 3 Poster
Pacific Ballroom H-O
Sat, 27 Aug, 19:30 - 21:30 Pacific Time (UTC -8)
To forage in a changing and uncertain environment, animals need to gather information about hidden states of the world to guide decisions. To understand the strategies that animals use in such settings, typical theoretical approaches combine Bayesian inference and value iteration to derive optimal behavioral policies that maximize total reward given changing beliefs about the environment. However, specifying these beliefs requires infinite numerical precision; with limited resources, this problem is no longer cleanly separable into components of inference and action selection. To understand the space of behavioral policies in this constrained setting, we enumerate and evaluate all possible behavioral programs that can be constructed from just a handful of states. We show that only 65 (1.4%) of the 4492 top-performing programs can be constructed by approximating Bayesian inference; the remaining programs are structurally or even functionally distinct from Bayesian. We develop a novel tree embedding to understand relationships between these programs. This embedding reveals hidden structures within the space of programs—with nearly all of the top-performing programs connected through single mutations—that can be used to efficiently search for good programs via evolutionary algorithms.