Explore or Exploit? A Generic Model and an Exactly Solvable Case

Finding a good compromise between the exploitation of known resources and the exploration of unknown, but potentially more profitable choices, is a general problem, which arises in many different scientific disciplines. We propose a stylized model for these exploration-exploitation situations, including population or economic growth, portfolio optimization, evolutionary dynamics, or the problem of optimal pinning of vortices or dislocations in disordered materials. We find the exact growth rate of this model for treelike geometries and prove the existence of an optimal migration rate in this case. Numerical simulations in the one-dimensional case confirm the generic existence of an optimum.

Figure 1

Comparison of simulations of Eq. (5) (blue triangles) and of Eq. (6) (red squares) for $N=512$ and $\tau =0.1$, as functions of the branching (diffusion) rate $J$. We fix $\sigma =1$. The dashed black line is the large $J$ asymptotics obtained from perturbation theory, $c(J)\approx {\sigma }^2/4\sqrt{J\tau }$. The dotted line reveals the $J^{-1}$ behavior of $c(J)$ for large $J$, predicted by the tree approximation (with $a=1/2$ and $m=1$).

Figure 2

Comparison of simulations of Eq. (6) for various $N$ and $\tau$, as a function of the branching (diffusion) rate $J$. Green diamonds, orange squares, and blue circles were obtained from numerical simulation of Eq. (6) for $\tau =0$, 0.1, and 1 with $N=2^{20}$. Blue triangles correspond to $\tau =1$ and $N=2^8$. In all cases, $\sigma =1$ and $a=1/2$, $m=1$. The solid curves were obtained by numerical solution of Eq. (15) for the corresponding values of $\tau$. The dashed gray lines are the large- and small-$J$ asymptotics.