The convergent evolution of warning signals in unpalatable species, known as Müllerian mimicry, has been observed in a wide variety of taxonomic groups. This form of mimicry is generally thought to have arisen as a consequence of local frequency-dependent selection imposed by sampling predators. However, despite clear evidence for local selection against rare warning signals, there appears an almost embarrassing amount of polymorphism in natural warning colors, both within and among populations. Because the model of predator cognition widely invoked to explain Müllerian mimicry (Müller’s “fixed nk” model) is highly simplified and has not been empirically supported; here, we explore the dynamical consequences of the optimal strategy for sampling unfamiliar prey. This strategy, based on a classical exploration–exploitation trade-off, not only allows for a variable number of prey sampled, but also accounts for predator neophobia under some conditions. In contrast to Müller’s “fixed nk” sampling rule, the optimal sampling strategy is capable of generating a variety of dynamical outcomes, including mimicry but also regional and local polymorphism. Moreover, the heterogeneity of predator behavior across space and time that a more nuanced foraging strategy allows, can even further facilitate the emergence of both local and regional polymorphism in prey warning color.