acceptodds
Withdrawn from ICLR 2027

Effective-Resistance Exploration in Monte-Carlo Graph Search

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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 convergence rate of the root value estimate for a fixed planning horizon, where 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.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, planning, spectral graph theory, sequential decision making

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_oWNAOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

How should we use MCTS on graphs? One option is to use a transposition table, the standard approach for using tree algorithms on graphs, as old as Computer Chess. But how in stochastic domains, with MCTS? Motivated by the Physics principle of electrical resistance, a new exploration rule is introduced and analyzed, for pooling successor states' counts, using an exploration bonus. The paper contains lengthy proofs in the appendices, 60 pages in total.

Critical strengths
  • the theoretical result on the computational complexity of the algorithm for Monte Carlo Graph Search may be correct and interesting
Critical weaknesses
  • limited, theoretical result, that builds on previous algorithm: Power-UCT.
  • 60 pages of proofs with no empirical results besides toy examples, this is not an ICLR paper
  • the proofs are claimed to be checked by an AI, but its name and the prompts are missing from the paper, appendix and supplementary material

This builds on a previous algorithm, Power-UCT. The contribution of the paper is a theoretical analysis that convergence rate holds as for Stochastic Power UCT. Also, there are numerical simulations and a toy-example (Frozen Lake, Passenger Grid, Four Rooms) of tabular grid size. There are no significant empirical results or experiments with real-world applications or games. There is also no ablation study, or a discussion where this algorithm can be used, and what the advantages are, not a comparison against alternative methods.

The theoretical analysis is checked by the authors by unspecified AIs, no prompts are provides for this check. No indication is given as to how surprising these results are from a theoretical perspective.

Questions for authors

The contribution is interesting, the idea is nice, but the result and lack of experimentation/application is too limited to be accepted. I could not find the LLM prompts for the proof checking, or the results, in the reproducibility information.

Reviewer_SFopOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies exploration in Monte Carlo graph search when different paths reach the same state at the same planning depth. It introduces a bonus that combines an action's own visit count with visits pooled at its successors. The analysis covers historical backups, which retain child estimates recorded on earlier visits, and establishes convergence and action-recommendation guarantees for power-mean and regularized graph search. The appendix examines the additional difficulties of merging states across depths. Numerical experiments evaluate several variants on stochastic planning tasks.

Critical strengths

The treatment of historical backups is the strongest contribution. A parent's estimate contains child values recorded at different times, while simulations through other parents continue to update those children. Theorem 6 and Lemma 11 handle this dependence through bounds that remain valid over later visits and a comparison between local and pooled counts. This supports the convergence arguments and extends the analysis to shared search statistics.

The exploration rule distinguishes evidence about an action's reward and transitions from evidence about its successors, using counts already stored by graph search. The paper also explains the limitations of sharing clearly. Its cyclic example shows how merging visits across depths can change the limiting value and slow convergence, and the regularized analysis accounts for the change in the planning objective. These results make the scope of the guarantees explicit.

Critical weaknesses

The central concern is the limited evidence for the benefit of the shared-successor term. The convergence guarantee applies to a broad class of additional inverse-count bonuses, and the regularized analysis relies on lower bounds for action-sampling probabilities. The resistance identities and cumulative-bonus bound also leave the effect on planning accuracy open. The numerical experiments include comparisons with and without ER for Power-UCT. The regularized methods all include ER, and the highlighted full-state results combine several algorithmic changes. Matched comparisons with the same representation and regularizer, including a bonus based only on the local action count, are needed to establish what the successor term contributes.

The experimental description does not make clear which experiments were completed and which implementation was used. Section 6 presents numerical results, while the reproducibility statement says that the experiments and final implementation remain to be completed. Appendix I refers to a coefficient sensitivity study that is absent from Section 6. Several tested configurations require further explanation of their relationship to the theory, especially the maximum-value backups and full-state search on cyclic domains. Appendix H gives episode limits for undiscounted runs, with the F+ planning-horizon rule left unspecified. A consistent account of the completed experiments and their implementation is needed to assess the practical claims.

Questions for authors

The implementation details that would most affect the assessment are the planning horizon used at each budget, the use of a fixed or evolving reference policy in RENTS, and whether search follows the full-depth historical-backup procedure analyzed in the paper. Clarifying these choices would help determine which guarantees apply to the reported variants. The theoretical contribution would also benefit from a direct comparison with Painter et al., Monte Carlo Tree Search with Boltzmann Exploration, NeurIPS 2023. That work uses a constant action-probability lower bound and depth induction to obtain exponential concentration. The additional contribution of the present analysis for historical backups and shared-successor estimates should be stated precisely.

Reviewer_mUgzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies exploration in graph-based Monte Carlo Tree Search (MCTS), where multiple actions may lead to the same successor state. The authors argue that existing graph-search methods may over-explore actions whose successor states have already been extensively explored through other paths, since exploration bonuses are primarily driven by local action visitation counts. To address this issue, the paper proposes an effective-resistance-inspired exploration bonus that incorporates both action-level and successor-state visitation statistics. The proposed bonus is integrated into GS-Power-UCT and regularized graph-search frameworks, for which the paper provides convergence analysis and empirical evaluation on several stochastic benchmark environments.

Critical strengths
  • The distinction between local action uncertainty and shared successor evidence is intuitive, and the proposed bonus is inexpensive to compute from existing counts.
  • The paper is supported by a solid theoretical analysis. The authors establish convergence guarantees for the proposed ER-based exploration framework and extend the analysis to regularized graph-search variants, providing theoretical support for the proposed approach.
Critical weaknesses
  • The paper motivates ER as a way to improve exploration efficiency by reducing redundant exploration of shared successor states. However, the theoretical results establish preservation of existing convergence guarantees rather than an improved convergence rate or sample-complexity result. Consequently, the claimed efficiency benefit remains primarily an empirical observation.
  • The experiments do not clearly isolate the contribution of the ER bonus. The strongest empirical results combine multiple design choices, including state merging, regularization, and ER-based exploration, making it difficult to determine how much of the observed gain is attributable to the proposed exploration mechanism itself.
Questions for authors
  • Can the authors provide matched ER/no-ER comparisons for the regularized variants, together with uncertainty estimates, to better isolate the contribution of the proposed exploration bonus?
  • Under what graph structures or problem characteristics do the authors expect ER-based exploration to provide the largest benefit?
Reviewer_UrFLOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper describes two new algorithms, GS-Power-UCT-ER and GS-E3W-ER. The work is based on the GS-Power-UCT algorithm. The algorithms extension considers a bonus term affecting exploration. It increases the probability of choosing actions that tend to lead to underexplored children nodes. Theroretically proven convergence bounds are given for the new algoritms. GS-Power-UCT-ER preserves GS-Power-UCT's O(1/n)O(1/\sqrt{n}) root value convergence rate, and GS-E3W-ER has a similar convergence rate in nn. The results are supported by numerical evaluation on four different benchmark problems, where the improvements are significant compared to GS-Power-UCT variants.

Critical strengths

The paper describes the modified algorithms clearly and it's easy to read. The algorithms have analytically computed and theoretically proven convergence bounds. The results seem to be sound, even though I didn't check the proofs in the appendix in detail. The results are supported by experiments. The experiments use 4 of the 5 benchmark problems that were used in GS-Power-UCT article, making a comparison easy and the improvement clear. The improvements on the benchmark problems are significant.

Critical weaknesses

None

Questions for authors

The behavior of the different algorithms variations is different on the benchmark problems. Is it possible to explain this by the different nature of the benchmark problems? Is it possible predict which algorithm will be the most effective, based on the structure of each benchmark problem? If it's possible to determine the cause, I think it would be worth to add a sentence about why GS-Power-UCT-F+ dominates the results for smaller budgets in FactoredRiverSwim. If it's not possible to determine it, the article is good as-is.

Comments on the paper

1 comment

Dear Area Chair and Reviewers,

Thank you for your time, effort, and constructive feedback on our submission. We truly appreciate the thoughtful insights and detailed comments provided during the review process, which have been invaluable in helping us identify areas for improvement.

After careful consideration of the reviews and our current results, we believe that the manuscript requires additional experiments and further empirical validation to fully substantiate our claims and strengthen the overall contribution. To ensure the work meets the high standards of ICLR, we have decided to withdraw the paper at this stage and dedicate more time to conducting these comprehensive experiments for a future submission.

Thank you once again for your support.

Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.