The "Finding a Restaurant" Problem

There's a toy problem I thought of while walking around Oakland (which, at least where we were, was a grid) that I tweeted about, but felt like writing more. Basically, my friend and I were trying to get food in Oakland while attending an event, and he was being dumb about not using Google Maps to decide where to get food first so we basically just decided to walk around until we found something we liked. We wanted to go back to the event afterwards, so e.g. walking in a straight direction was not the right thing to do, and we walked in a spiral instead, but was this the best thing to do?

Here's a model for this scenario: You start at (0, 0) on the integer 2-D lattice. You walk on some path consisting of only orthogonal moves on the 2-D lattice (so up/down/left/right moves only). Every time you visit a new point on the lattice, you have a probability p chance of "finding a restaurant you like", at which point your path ends and you return to the origin (using the shortest path of only orthogonal moves, i.e. if you find the restaurant at (x, y) you move |x|+|y| steps back to the origin). What path minimizes the expected number of steps you take? (Both on the way to the restaurant and back to the origin, though if the path only visits new locations, it's equivalent to just minimize the expected length of the path to the origin).

The conjecture is that the "spiral" (up 1, right 1, down 2, left 2, up 3, right 3...) is the optimal path, but it's unclear (at least to me) how to prove it. Namely, this seems to be a greedy strategy, but it's unclear what exchange argument if any proves it.

If we are allowed diagonal moves, even just on the way back, or the grid is isometric instead, it's fairly straightforward to show the spiral is correct: You visit all the locations distance i from the origin before spending any time visiting a location distance i+1 from the origin, and you waste no time visiting new locations, so given any other path, via an exchange argument you can show the expected number of steps the spiral takes is better than the other path's.

We can also show the spiral is a 3/2 approximation, using the fact that the spiral is optimal if we are allowed diagonal moves on the way back, as the ratio between any solution's expected cost if allowed diagonal moves and its actual expected cost differ multiplicatively by at most 3/2. 3/2 comes from the fact that you pay a factor of at most 2 on the path back to the origin, but the path back comprises at most half your total length.

Furthermore, the ratio between expected costs can easily be improved to some function of p with domain (1, 3/2) with a more refined analysis, since at most points in the spiral the distance to the origin is much less than the distance walked to reach that point and/or we are losing much less than a factor of 2 on the way back to the origin, and my guess is that this constant will end up being very close to 1 for lots of p, effectively resolving the problem for (limited) practical purposes. However, this analysis alone still falls short of proving optimality.