  The time it takes a random walker in a lattice to reach the origin from
another vertex $x$, has infinite mean. If the walker can restart the walk at
$x$ at will, then the minimum expected hitting time $T(x,0)$ (minimized over
restarting strategies) is finite; it was called the ``grade'' of $x$ by
Dumitriu, Tetali and Winkler. They showed that, in a more general setting, the
grade (a variant of the ``Gittins index'') plays a crucial role in control
problems involving several Markov chains. Here we establish several conjectures
of Dumitriu et al on the asymptotics of the grade in Euclidean lattices. In
particular, we show that in the planar square lattice, $T(x,0)$ is asymptotic
to $2|x|^2\log|x|$ as $|x| \to \infty$. The proof hinges on the local variance
of the potential kernel $h$ being almost constant on the level sets of $h$. We
also show how the same method yields precise second order asymptotics for
hitting times of a random walk (without restarts) in a lattice disk.
