- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies whether policy-gradient training with a two-head transformer can search a hidden tree. With DFT, the training learns to avoid some actions and backtracking. The results also generalizes from depth-1 and depth-2 trees.
Critical strengths
-
The paper gives a nontrivial analysis connecting policy-gradient updates to a search mechanism.
-
The explanation of why depth-1 training fails to generalize, and how depth-2 training corrects the parameter imbalance, is particularly interesting.
Critical weaknesses
- The environment does not repeated actions, which forces successful policies to follow DFS. With the predefined head roles, it's confusing on whether this significantly restrict the policy search space.
- The analysis requires careful constructions of the transformer. While this isn't unusual for related works in the literature, I wonder if this theoretical construction is validated to perform well empirically (maybe i'm missing this information from appendix E).
Questions for authors
- Since the no-repeat rule forces successful policies to follow DFS, which insights from the analysis are expected to extend to environments allowing revisits and other search strategies?
Response to Reviewer s4k7
We thank the reviewer for the positive assessment and for recognizing the contribution of our policy-gradient analysis. We clarify the two concerns below.
An important distinction is that the no-repeat rule does not enforce DFS at the policy level. In particular, illegal actions are not masked from the transformer's output distribution (Eqs. 9–10). The agent can still select previously tried actions or backtrack prematurely, resulting in failure. Thus, the policy must learn to suppress these actions and identify when backtracking is appropriate, solely through terminal reward.
Moreover, the predefined head roles do not hard-code the search algorithm: the attention and output matrices B,C,P,Q are learned from zero initialization. Indeed, Theorem 2 shows that depth-1 training fails to generalize despite learning basic backtracking and action avoidance, while Theorem 3 establishes that depth-2 training learns the missing internal-node backtracking mechanism and generalizes to deeper trees. This distinction is central to our contribution.
The key transferable insight is how RL trains attention to retrieve action histories and failure outcomes, and combines them into search decisions (Theorem 1, Fig. 2).
In our static-tree setting, revisiting an already explored branch provides no new information, so redundant revisits are unnecessary for efficient search. If revisits were permitted, avoiding such redundant exploration would remain beneficial. More generally, while richer environments may favor other search strategies, the learned primitives of history-dependent action selection and outcome-conditioned backtracking remain relevant.
Our imbalanced extension already demonstrates that the framework is not limited to uniform random DFS: Proposition 2 and Theorem 4 establish ranked DFS, which prioritizes more promising branches to minimize expected search length.
We indeed provide empirical validation in Appendix E, using stochastic policy gradient with batch size 256 rather than the population gradients assumed in the analysis.
These experiments support both the predicted training dynamics and depth generalization, rather than merely verifying that the hand-constructed parameters can execute DFS.
We hope these clarifications address the concerns and further highlight that our main contribution is explaining how RL learns the search mechanism, rather than assuming it is already present.