Consider a random walk on an undirected graph that keeps track of how many times it has visited every node. At each step, it moves to the node among its neighbors which has been visited the least number of times. If there are several such nodes, it chooses one at random. My question is: what is the (worst-case) cover time of this random walk as a function of the number of nodes $n$?
The answer should be at least $\Omega(n^2)$. Consider a star graph where each node has a self-loop. In this graph, the walk starting at the center will visit the leafs in some order, without loss of generality $1,2,3, \ldots, n-1$ (relabel the vertices if necessary). The time spent at leaf $i$ will be at least $i-1$ because the center will have been visited $i-1$ times before leaf $i$. Thus the total cover time will scale as $\Omega (n^2)$. If we want an example without self-loops, we can consider a star-like graph where each leaf is replaced by a path of length $2$.
Alternatively, what is the largest hitting time between any two vertices for this random walk? This feels like asking a very similar question.
For the usual random walk which jumps to each out-neighbor, the largest hitting time will be $O(n^3)$ but the standard proofs rely on resistances, which are not applicable here due to lack of reversibility.