Many recent policy-gradient methods learn without a value network. Each update samples a group of attempts at the same task and scores each attempt against the group's average. Group Relative Policy Optimization (GRPO) is the best-known example. These methods treat every attempt as an isolated chain of actions. In puzzles, assembly tasks, and tool-using agents, though, different attempts often pass through exactly the same intermediate state by doing independent steps in a different order. Board-game search engines exploit this with a transposition table: a hash map that recognises "I have seen this position before, by another move order" and merges the two branches. We propose bringing that idea into the policy-gradient estimator. Within each sampled group, hash the environment states the attempts visit, merge them into a graph, and score every step by comparing the average outcome of all attempts that passed through the state it reached with the average outcome of all other attempts that passed through the state it left.
This matters most when reward is sparse. If one attempt in sixteen succeeds, a group-average estimator gives the fifteen failures one identical negative score, and every step of the success the same positive score. With merging, a failed attempt that reached a state on the successful path gets positive credit for the steps that got it there and negative credit only for where it went wrong afterward. That is step-level credit assignment obtained from rollouts already paid for, with no learned critic and no extra branched simulations.
Core Claim
In environments with exact, hashable Markov state, pooling outcomes across rollouts that meet at the same state gives step-level advantage estimates with three properties. They are unbiased. Their variance falls roughly with the number of rollouts sharing each state. They separate the gradient into many distinct directions, rather than the near-rank-2 update documented for group baselines. The expected gain is governed by one measurable quantity, the confluence rate: the fraction of steps whose state is also visited by another rollout in the same group. Theory on permutation redundancy predicts this rate should be high exactly where many actions commute.
Concretely, let rollout $i$ visit state $s_t$, take action $a_t$, and reach $s_{t+1}$. Let $\bar G(s)$ be the mean return-to-go over all rollouts in the group whose first visit to $s$ occurs, measured from that visit. Let $\bar G_{-i}(s)$ be the same mean excluding rollout $i$. With deterministic transitions and zero intermediate reward, the transposition-pooled advantage is
$$ \hat A_{i,t} = \bar G(s_{t+1}) - \bar G_{-i}(s_t), $$
falling back to the group's leave-one-out mean when no other rollout visits $s_t$. Two facts justify unbiasedness. Returns from a state are conditionally independent of how a rollout got there, which is the Markov property. The baseline excludes the rollout's own return, so it does not depend on the rollout's own action. If $k$ rollouts share $s_{t+1}$, averaging $k$ conditionally independent returns cuts the variance of the first term by about $1/k$. The time limit has to be part of the hashed state, otherwise returns from the "same" state differ in remaining horizon. We will prove these statements and check them numerically against brute-force gradients on small instances.
This resolves a tension the literature leaves open. Monte-Carlo Graph Search (Improving AlphaZero Using Monte-Carlo Graph Search) merges transposed board positions inside AlphaZero's search tree. It reports about 310 Elo in Crazyhouse and 69 Elo in chess, but it needs special edge/node bookkeeping to avoid double-counting values that flow back through shared nodes. It never touches the policy-gradient estimator. The worry is that merging paths whose histories have different action probabilities might bias a gradient. Our answer is that only the score of each step is pooled. Each step's own gradient term $\nabla_\theta \log \pi_\theta(a_t \mid s_t)$ is left untouched, so no path probability is ever shared.
Relation to Prior Work
Three lines of work motivate the proposal.
The first shows the gap in group-baseline methods. On the Policy Gradient Foundations of Group Relative Policy Optimization analyses GRPO under outcome-only reward. It shows every token gets the same advantage, the gradient's effective rank stays near 2 for group sizes 2 to 8, and group baselines are biased in multi-turn settings. It diagnoses the problem but treats rollouts as independent chains. We keep the group but let rollouts share credit where they meet, and we use its rank measurement directly as a diagnostic.
The second supplies the closest competitor. Segment Policy Optimization obtains segment-level credit by launching extra Monte Carlo completions from low-confidence cutpoints, as chains or trees, and reports 6–12 point gains over PPO/GRPO on GSM8K and 7–11 over GRPO on MATH500. Its tree treats every branch as distinct and pays extra rollouts for its estimates. Our estimator needs no extra rollouts but helps only when natural confluence occurs. Each method therefore has a regime where it should win, and we test both.
The third supplies the mechanism and its limits. Transposition merging (MCGS) and value-offset abstraction (KVDA-UCT) group nodes inside search trees. KVDA-UCT is provably lossless only in deterministic domains and warns that relaxed equivalence in stochastic ones produces faulty abstractions. That constrains us to exact hashing for the main claim, with approximate merging treated only as a stress test. Partial order reduction in planning (K∗ and Partial Order Reduction for Top-Quality Planning) explains why confluence is common: $n$ independent actions admit up to $n!$ orderings that end in one state. We use it as an analysis lens to predict confluence, not as a pruning step.
On the exploration side, First return then explore shows that remembering visited states (as coarse cells) is decisive under sparse reward. Go-Explore uses its archive for resets and imitation, not for gradient credit. Our within-group graph is a short-lived, on-policy cousin of that archive.
Research Program
The work has four parts.
Estimator and theory. We will state and prove the unbiasedness and $1/k$ variance results for deterministic Markov environments with first-visit pooling and time-augmented hashes. We will also characterise the bias that appears under stochastic transitions, where $Q(s,a)$ is no longer $\bar G(s')$, so we must pool at the (state, action) level instead.
Implementation. The estimator plugs into a standard GRPO-style trainer. During rollout generation each environment state is hashed (Zobrist-style for grids, canonical serialisation otherwise). After the group finishes we build the confluence graph and compute $\hat A_{i,t}$. A per-group hash table should add little overhead relative to policy inference. The file reports roughly 1% runtime overhead for KVDA-UCT's search-time bookkeeping, which is a related but not identical setting, and we will measure our own overhead.
Confluence analysis. Before any training, we measure confluence rates under the initial policy across environments. Using commuting-action counts in the spirit of partial order reduction, we test whether the predicted rate matches the observed one.
Gradient diagnostics. We replicate the singular-value analysis of the GRPO paper to test whether pooled advantages raise the gradient's effective rank.
Baselines
The naive reference is GRPO with a leave-one-out group baseline. Every step of a rollout gets that rollout's return minus the mean of the other rollouts' returns. Our estimator reduces to exactly this when no states are shared, so it isolates the contribution of merging. It will use identical group size, sampling temperature, learning rate sweep, and environment-step budget. The GRPO analysis paper reports its effective-rank value of about 2 on GSM8K. No reported success-rate number for GRPO on our planning environments was found on Lacuna.
The strongest critic-based competitor is PPO with a learned value network and generalised advantage estimation. A network that sees identical states should output identical values, so it is the obvious way to get step-level credit. It gets the same environment steps and a matched hyperparameter search budget over critic learning rate and GAE parameters. Its extra memory and compute for the critic are reported rather than hidden. The file reports PPO trailing SPO by 6–12 points on GSM8K and PPO scoring zero after 1 billion frames on sparse Fetch pick-and-place (First return then explore). Neither is a number on our environments.
The strongest critic-free competitor is SPO-tree (Segment Policy Optimization). It buys step-level credit with additional branched completions. The comparison is run at equal total environment steps, so SPO-tree's extra completions come out of its group size. This is the comparison that decides whether natural confluence is a cheaper source of credit than manufactured branching. We also run SPO-tree with transposition merging added to its branches, since the two are complementary.
The ablation isolating the key ingredient is shuffled merging. We merge nodes at random while keeping the same confluence statistics, which shows whether the benefit comes from genuine state identity or merely from averaging. A second ablation is the persistent tabular table described below.
Beating a baseline means a higher solved-instance rate at the same environment-step budget, with non-overlapping confidence intervals over at least five seeds, and lower measured gradient variance per step.
Why not just…?
Why not just use PPO's learned critic, which already generalises across identical states? In principle a critic learns $V(s)$ and gives the same credit. Under sparse reward, though, its targets are almost all zero early on. Learned critics in policy optimisation feed non-stationary, biased targets back into the update (Fujimoto et al.), and critic-based PPO trailed critic-free SPO on GSM8K. Our pooled estimate is exact for the current policy the moment two rollouts meet. The real threat is that on short-horizon procedurally generated Sokoban a critic may learn fast enough to match us. The equal-budget PPO comparison, and learning curves in the first tenth of training where critics are least reliable, settle this.
Why not just keep a persistent hash table of average returns per state across training, a tabular critic? This is the simplest version of our idea and a genuine threat. Its statistics come from older policies, so they are biased toward stale behaviour, but they also cover far more visits. We include it with exponential decay as an ablation. If it matches or beats within-group pooling, we will report that a decayed hashed tabular critic is sufficient, and the contribution becomes the confluence analysis explaining when it helps.
Why not just enlarge the group? The GRPO analysis finds effective rank stays near 2 as group size grows from 2 to 8. Larger groups sharpen the same two directions rather than localising credit. Larger groups also raise confluence, though, which helps our method too. We therefore sweep group size for both GRPO and our estimator and compare at equal environment steps.
Why not just use Go-Explore-style archives and resets? Go-Explore needs a resettable simulator and a separate imitation phase, and it solves a different problem: reaching the frontier at all. Our estimator is about extracting credit once some rollouts succeed. The two compose naturally, by training from archive resets with pooled advantages, and we treat that combination as an extension rather than a competitor.
Proposed Experiments
Sokoban. We train convolutional policies from scratch on procedurally generated levels with varying box counts, following the reduced-box practice boards used in A Novel Automated Curriculum Strategy to Solve Hard Sokoban Planning Instances. We then evaluate on its set of 225 hard instances. That paper reports 30/225 (13%) for its CNN baseline and 179/225 (80%) for its full MCTS-plus-curriculum system. Those are external reference points from a search-based system, not like-for-like baselines, and we will say so. Within our policy-gradient comparisons, the prediction is that gains grow with box count, because more boxes means more commuting pushes and higher confluence.
Sequential brick assembly. We use the ModelNet40 shapes and environment of Budget-Aware Sequential Brick Assembly, where placement order is highly permutable. A sparse reward is given on final 3D IoU. That paper reports 0.599 IoU on airplanes for BrECS, a supervised-plus-search method, again as an external reference.
Multi-turn language-model agent. We fine-tune a small open model acting in text Sokoban. The environment state, not the text, is hashed. This directly tests the multi-turn bias the GRPO analysis identifies in group baselines.
Stress test with approximate merging. We use Go-Explore-style downscaled cells on Montezuma's Revenge to measure how bias grows when equivalence is approximate. We expect this to degrade, consistent with KVDA-UCT's warning about faulty abstractions.
Decisive checks. Across these environments there are four.
The first is unbiasedness. Pooled gradients should match exact gradients on enumerable small instances within Monte Carlo error.
The second is a dose-response relation. Improvement in success rate and reduction in per-step gradient variance should increase with measured confluence rate across environments and box counts. If gains appear without confluence, something other than our mechanism is at work.
The third is rank. Effective gradient rank should rise above GRPO's value of about 2 in proportion to confluence.
The fourth is the shuffled-merge ablation. It should erase the gains.
If confluence turns out to be rare under realistic policies (for example, if trained policies quickly settle on one ordering), the method's benefit is confined to early training. That outcome is itself worth reporting as a limit on transposition-based credit in learning, as opposed to search.
References
- Improving AlphaZero Using Monte-Carlo Graph Search
- On the Policy Gradient Foundations of Group Relative Policy Optimization: Credit Assignment, Gradient Sparsity, and Rank Collapse
- Segment Policy Optimization: Effective Segment-Level Credit Assignment in RL for Large Language Models
- Grouping Nodes with known Value Differences: A lossless UCT-based Abstraction Algorithm
- K∗ and Partial Order Reduction for Top-Quality Planning
- First return then explore
- Addressing Function Approximation Error in Actor-Critic Methods
- A Novel Automated Curriculum Strategy to Solve Hard Sokoban Planning Instances
- Budget-Aware Sequential Brick Assembly with Efficient Constraint Satisfaction