Effective-Resistance Exploration in Monte-Carlo Graph Search

Monte-Carlo graph search shares samples across different paths that reach the same state. This sharing also changes what remains worth exploring: an action may have been selected only a few times even though its successor states have already been extensively explored through other paths. We study how exploration should respond to this shared evidence in stochastic planning. Motivated by effective resistance, we introduce an exploration rule that combines an action's own visit count with the evidence pooled at its successor states. Visits through one path can therefore reduce exploration pressure along other paths leading to the same state, while each action retains a separate incentive for local exploration. Building on graph-based Power-UCT, we establish conditions under which this rule preserves the $O(n^{-1/2})$ convergence rate of the root value estimate for a fixed planning horizon, where $n$ is the number of simulations. We also extend the approach to entropy-regularized graph search and quantify how sample sharing reduces an upper bound on cumulative exploration bonuses. The resulting framework makes exploration explicitly responsive to evidence collected across the search graph.