  Self-interacting random walks are endowed with long range memory effects that
emerge from the interaction of the random walker at time $t$ with the territory
that it has visited at earlier times $t'<t$. This class of non Markovian random
walks has applications in a broad range of examples, ranging from insects to
living cells, where a random walker modifies locally its environment -- leaving
behind footprints along its path, and in turn responds to its own footprints.
Because of their inherent non Markovian nature, the exploration properties of
self-interacting random walks have remained elusive. Here we show that long
range memory effects can have deep consequences on the dynamics of generic
self-interacting random walks ; they can induce aging and non trivial
persistence and transience exponents, which we determine quantitatively, in
both infinite and confined geometries. Based on this analysis, we quantify the
search kinetics of self-interacting random walkers and show that the
distribution of the first-passage time (FPT) to a target site in a confined
domain takes universal scaling forms in the large domain size limit, which we
characterize quantitatively. We argue that memory abilities induced by
attractive self-interactions provide a decisive advantage for local space
exploration, while repulsive self-interactions can significantly accelerate the
global exploration of large domains.
