Localization Transition Induced by Learning in Random Searches

We solve an adaptive search model where a random walker or Lévy flight stochastically resets to previously visited sites on a $d$-dimensional lattice containing one trapping site. Because of reinforcement, a phase transition occurs when the resetting rate crosses a threshold above which nondiffusive stationary states emerge, localized around the inhomogeneity. The threshold depends on the trapping strength and on the walker’s return probability in the memoryless case. The transition belongs to the same class as the self-consistent theory of Anderson localization. These results show that similarly to many living organisms and unlike the well-studied Markovian walks, non-Markov movement processes can allow agents to learn about their environment and promise to bring adaptive solutions in search tasks.

Figure 1

Average total number of visits to the starting site ${\mathbf{x}}_0=(-5,5)$ (green triangles) and to the inhomogeneity (blue diamonds) as a function of time, for a $2d$ walker with $q=0.2$ ($\gamma =0.9$). At early times, the walker slowly diffuses around ${\mathbf{x}}_0$ (orange light disk in the insets). After the inhomogeneity (red dark disk) has been found, it becomes steadily revisited, indicating spatial learning and localization.

Figure 2

$P_0$ as a function of $q$ in $1d$ with NN hopping. Solid lines are given by Eq. (8) and symbols by Monte Carlo simulations of the rules (a) and (b) (at $t={10}^5$).

Figure 3

Phase transition in $1d$ for Lévy flights with $\mu =1/2$. Left: The thick (black) solid lines are given by Eq. (5) for the $t=\infty$ limit, and the symbols by simulations up to different times $t$ ($\gamma =0.9$). The parameter $\tau$ is explained in the text. Right: $P_0$ for $\gamma =0.9$, 0.8 and 0.7, where theory predicts $q_c\approx 0.0803$, 0.1642, and 0.2519, respectively ($t={10}^5$ in simulations).

Figure 4

Phase diagram in $1d$ for various Lévy indexes.

Figure 5

Asymptotic probability of presence in $1d$ for Lévy flights with $\mu =1/2$. The solid line is the inverse Fourier transform of Eq. (4) and symbols represent simulations.