acceptodds
Under review as a conference paper at ICLR 2027

Tropical Reinforcement Learning

Abstract

Reinforcement learning for large language models typically maximizes expected return, adding up the probabilities of all successful trajectories. However, the classical sum formulation can only report how often the model policy succeeds, not which solution actually worked, and because probabilities sum to one, reinforcing one solution can make the model forget another that was never shown to be wrong. This makes expected return a poor fit for compositional reasoning, where a solution must be assembled from reasoning steps that the model produces in separate, often failed, attempts but rarely produces together. To address this, we propose Tropical Reinforcement Learning, which rests on a simple change of algebra: instead of adding the probabilities of alternative solutions, we take their maximum, which yields the tropical semiring. The value of a state then becomes the log-probability of its most likely verified solution, together with an explicit path that can be replayed and reused. This enables true composition, since the best prefix and the best suffix meeting at a shared state can be joined even when they come from different rollouts. To put this into practice, we introduce Tropic, a training algorithm for deterministic, resettable environments with verifiable outcomes. On four agentic tasks (Sokoban, Countdown, FrozenLake, WebShop), Tropic outperforms the strongest on-policy baselines by up to 16 percentage points. Changing the algebra of reinforcement learning, not just its estimators, can thus substantially improve compositional reasoning in language models.

Primary area:
reinforcement learning
Keywords:
RL, LLMs, Composition

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_bzEDOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

The paper studies LLM-agent tasks with deterministic, resettable environments and verifiable outcomes. TROPIC stores states and actions from multiple attempts, including valid transitions from failed attempts. When two trajectories reach the same state, it concatenates a prefix from one trajectory with a suffix from another. The resulting complete path is replayed from the initial state and accepted by the verifier before being used for maximum-likelihood training.

The paper proposed a method named Tropical Reinforcement Learning. For each problem, TROPIC maintains a graph of valid transitions discovered across multiple attempts, including transitions from failed attempts. When two attempts reach the same state, TROPIC can join a prefix from one attempt with a suffix from another. It then replays the resulting complete path from the initial state and adds the path to the archive only if the verifier accepts it. TROPIC also starts new attempts from frontier states, namely states that are reachable in the graph but do not yet have a verified completion. During training, it selects the best archived path and, when available, a coverage path containing transitions that have been trained less often, and applies maximum-likelihood updates to these paths. The “tropical” part refers to how alternative verified paths are combined: their scores are combined by taking the maximum rather than summing their probabilities.

Experiments cover four environments and two model families. In Table 2, TROPIC outperforms the listed main baselines in every setting. At test time, archive, restarts, and composition are disabled, so the evaluation measures what has transferred into the model parameters. These results support the effectiveness of the complete TROPIC training procedure.

Critical strengths
  1. The method design is coherent and matched to the target setting. The use of a graph, an archive, composition, replay, and verification is appropriate for deterministic, resettable environments with verifiable outcomes.

  2. The empirical evaluation is broad and thorough. The paper covers four environments and two model families, reports results over three training seeds, and includes both main comparisons and component ablations.

Critical weaknesses
  1. The ablations do not isolate the contributions of the individual components. Disabling a component changes the search trajectory and the set of verified paths available for training, so the current ablations compare end-to-end variants rather than holding the training data fixed. In particular, the No Composition result cannot distinguish the benefit of composition itself from the benefit of the additional training paths created by composition. To isolate the training objective, the authors should apply alternative training rules to the same fixed archive of verified paths. The comparison should also report matched generated tokens, verifier and environment calls, replays, and optimization updates.

  2. The comparison with related work is incomplete. The paper compares against MaxRL, GiGPO, and GiGPO + T-STAR, but these comparisons do not use the same archive of verified paths, and Appendix C acknowledges that the actual compute is not matched. The paper also does not discuss [1] or [3], and does not provide a direct comparison with [2]. These works are not identical baselines, but they provide relevant search or self-training precedents that should be discussed when positioning the contribution.

[1] Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah D. Goodman. STaR: Bootstrapping Reasoning With Reasoning. NeurIPS 2022.

[2] Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. ReST-MCTS: LLM Self-Training via Process Reward Guided Tree Search.* NeurIPS 2024.

[3] Xinyu Guan, Li Lyna Zhang, Yifei Liu, Ning Shang, Youran Sun, Yi Zhu, Fan Yang, and Mao Yang. rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking. arXiv preprint arXiv:2501.04519, 2025.

  1. The tropical objective is not shown to align with task success rate. Equation 11 maximizes the log-probability of the most likely verified path, whereas task success rate depends on the sum of the probabilities of verified paths. Equation 10 gives only a lower bound and does not imply that task success rate must increase. The paper does not measure whether the maximum-path probability can increase while task success rate or the probability of other verified paths decreases. Moreover, the strongest theoretical guarantee assumes separate parameters at each state and a single-path update, which does not match the shared-parameter language model and the additional coverage path used in the implementation.
Questions for authors
  1. Contribution clarification: Relative to search plus self-training, is the main contribution the composition, the maximum-based objective, or their combination? Which results distinguish these possibilities? What's the difference between related work?

  2. Controlled comparison: Given a fixed archive of verified paths and a matched training budget, how does maximum-likelihood training on the best verified path compare with maximum-likelihood training on all deduplicated verified paths and with other ways of aggregating verified paths?

  3. Objective alignment: During actual training, are there cases where the maximum-path probability increases while the task success rate decreases? Can you track the degradation of other verified paths for the same problem?

  4. Root-Only clarification: Since Root-Only still permits composition between different root-started rollouts, please provide a concrete example of a Root-Only instance whose first verified solution was assembled from a prefix in one rollout and a suffix in another. And clarify how FIRST-SOLVE is counted in this case.

5 comments

Thank you for the review. We ran the fixed-archive experiment you proposed (Table R1). Please see the answers below.

Q1: What is the contribution?

The combination. Composition builds verified solutions from fragments of different attempts. The tropical (maximum-based) update decides which verified path the model is trained on. Table R1 tests each part with the training data held fixed:

  • Search plus self-training (uniform training on the archive, row C): 51.9%
  • Tropical update without composed paths (row A′): 48.7%
  • Composed paths with expected-return weighting (row E): 39.7%
  • Composed paths with the tropical update (row A): 58.6%

Neither part alone reaches the combination. The end-to-end ablation agrees: Full TROPIC reaches 58.4% on Sokoban against 40.8% for No Composition. Across all four tasks and both models, the gain from composition is 4.9–17.6 points (Tables R5a and R5b, response to Reviewer 5kND).

The two parts are also linked in the method. Joining a prefix and a suffix requires a value that names concrete paths. A sum over paths does not provide this (Observation 1), while the maximum does (Eq. 9). The difference from related work is addressed under W2.

W1 / Q2: Comparison on a fixed archive

The Table 3 ablations are end-to-end by design: they show what each component contributes to the full system. For fixed data, Proposition 3 gives the comparison analytically, as the weight each objective places on the same set of paths. Table R1 tests it empirically.

Protocol. We saved the graph and archive of every problem at every iteration of the TROPIC runs and trained each rule on this identical stream. The matched quantities are:

  • Generated tokens, environment calls, verifier calls, and composition replays: identical by construction, because all rules share the same acquisition.
  • Initialization, optimizer, and number of updates: identical.
  • Training tokens per update: 6.2–6.6k (last column).

Only the choice and weighting of training paths differ. The witness is the best (most likely) verified path of a problem. A composed path is a verified path that exists in the archive only through composition: it was assembled from parts of different attempts and not sampled in one piece. The third column is the share of update weight on such paths.

Table R1. Update rules trained on the same data (Sokoban, Qwen2.5-3B-Instruct, 3 seeds).

Update ruleSuccess (%)Weight on composed paths (%)Trained tokens per step (k)
A. Tropical, Eq. 14 (witness + coverage paths, unit weights)58.6 ± 1.839.86.4
A′. As A, with composed paths excluded from training48.7 ± 2.0–6.2
B. Tropical, witness only55.6 ± 1.947.16.3
C. Uniform over distinct archived paths (≈ rejection-sampling FT)51.9 ± 2.326.26.6
D. Probability normalized per problem (MaxRL weighting)54.0 ± 1.814.26.5
E. Raw probability Pθ(τ∣x)P_\theta(\tau \mid x) (expected return)39.7 ± 2.03.56.4
  • Best path versus all deduplicated paths (Q2). Training on the best verified path alone (B, 55.6%) is 3.7 points above training on all deduplicated paths (C, 51.9%).
  • Other aggregations (Q2). MaxRL weighting reaches 54.0% and expected-return weighting 39.7%. The full tropical update is highest at 58.6%, which is 4.6 points above MaxRL weighting and 18.9 above expected return. Expected return places only 3.5% of its weight on composed paths, against 39.8% for the tropical update.
  • Composition versus its training paths (W1). Row A′ removes composed paths from training while the acquisition stays identical. Success drops from 58.6% to 48.7%. These 9.9 points are the benefit of composed paths as training targets alone. In A′, a composed path is excluded only while it exists solely through composition. If it is later sampled directly, it becomes eligible.

The 9.9 points and the 17.6-point end-to-end gain measure different things and do not add up. End-to-end runs also differ in which paths are acquired afterwards.

Cost against the baselines. At matched model-token cost on Sokoban, TROPIC at half of its budget (45.8%) already exceeds SNR-Aware at the full budget (40.7%). See Table R4 in our response to Reviewer sof8. We will add the compute accounting to Appendix C.

W2: Related work

ReST-MCTS* is cited in Section 5 (Zhang et al., 2024) among the tree-search methods. We will add STaR and rStar-Math to that discussion. Their counterparts are already among our comparisons:

  • STaR generates attempts, keeps the correct ones, and fine-tunes on them. In our setting, this corresponds to No Composition, which Appendix C describes as archive-based exploration with rejection-sampling fine-tuning (40.8%), and to row C on the same archive (51.9%).

  • ReST-MCTS* and rStar-Math run a tree search guided by a separately learned process-reward or preference model. TROPIC differs in two ways:

    • Tree versus graph. A tree keeps its branches separate. TROPIC merges identical states reached by different attempts into a graph, which is what allows a prefix from one attempt to be joined with a suffix from another.
    • No additional learned model. TROPIC uses the actor's own log-probabilities and the verifier.

    A direct run of ReST-MCTS* would add a learned reward model that none of the compared methods uses.

On the same-archive and matched-compute points:

  • MaxRL: row D is the MaxRL objective on the same archive and budget (54.0% vs. 58.6%).
  • GiGPO and T-STAR: both keep the expected-return objective, and row E is that objective on the same archive (39.7%).
  • Compute: the statement in Appendix C concerns wall-clock time under different stopping rules. The rollout budget is matched for all methods.

W3 / Q3: Alignment with task success

What the paper shows. The success rate in Table 2 is single-attempt task success on 512 held-out instances, and TROPIC is highest in all eight settings. The paper claims no guarantee beyond this: Section 4.2 states that the bound of Eq. 10 "does not by itself force pass@1 up."

What we measured in addition. Across consecutive training checkpoints on Sokoban, we tracked three quantities on a fixed reference archive, so that newly added paths cannot inflate the numbers:

  1. the best-path probability;
  2. the summed probability of all archived verified paths;
  3. the success rate, estimated by repeated sampling on the same problems.

Table R8. Tropical value and success (Sokoban, Qwen2.5-3B-Instruct).

QuantityValue
Intervals with rising best-path log-probability in which sampled success did not fall (%)91.7
Intervals with rising best-path log-probability in which summed archived-path probability rose (%)88.9
Non-best verified paths losing at least half their probability (%)24.8
Spearman correlation between best-path log-probability and sampled success across problems0.76
  • Q3, first part: yes. In 8.3% of the intervals where the best-path probability rises, sampled success falls. In the other 91.7% it does not.
  • The sum follows the maximum. Task success depends on the summed probability of verified paths, as you note. This sum rises in 88.9% of the intervals where the best-path probability rises.
  • Q3, second part: other verified paths. 24.8% of non-best verified paths lose at least half their probability. This is expected, since the objective concentrates probability on the best path. For reference, under GRPO, 30.2% of the best verified paths themselves lose half their probability, against 6.8% under TROPIC (Table R7, response to Reviewer 5kND).

The alignment is therefore strong but empirical, and we will say so in Section 4.2.

Theory. Both gaps are stated in the submission. The text below Theorem 4 says that the theorem is exact only for separate parameters per state. Remark 1 says that the coverage path lies outside Theorem 12 and is a deliberate trade. In practice, the trade pays off: coverage paths raise success from 55.6% to 58.6% (rows B and A) and reduce the share of deteriorated probe paths from 15.4% to 6.8% (Table R7).

Q4: Root-Only and First-Solve

You are right, and no such example exists. In Root-Only, every attempt starts at the initial state, so any successful suffix already belongs to a complete successful attempt. A join can therefore never be the first verified solution.

On auditing the counter, we found that it measured a different quantity: the share of solved training problems whose best verified path is a join that was never sampled in one piece. We will rename the statistic to Best-Join and correct its definition and the statements that describe 24.7% and 31.6% as first solutions. No success rate is affected.

Where first solutions come from. The first verified solution of a problem has one of three origins:

  • Root-started rollout: sampled in one piece from the initial state.
  • Frontier-started completion: a stored prefix from an earlier attempt, completed by a new attempt started at its end state.
  • Graph join: a stored prefix joined with a stored suffix.

Table R9. Origin of the first verified solution (% of solved training problems; Sokoban, Qwen2.5-3B-Instruct, 3 seeds).

VariantRoot-started rolloutFrontier-started completionGraph join
No Composition63.836.20.0
Root-Only100.00.00.0
Successful-Only61.438.60.0
Full TROPIC55.944.10.0

In Full TROPIC, 44.1% of first solutions are frontier-started completions. These combine fragments of two attempts and were also never sampled in one piece.

What joins contribute. A join matters because it can be more likely under the current model than any sampled solution, and it then becomes the path the model trains on. A typical Root-Only case has three steps:

  1. Attempt 1 succeeds and passes through a state vv.
  2. Attempt 2 reaches vv by a more likely prefix, then fails.
  3. Joining the prefix of attempt 2 with the suffix of attempt 1 gives a verified path that was never sampled and is more likely than attempt 1.

Table R10. Contribution of joins to training paths (Sokoban, Qwen2.5-3B-Instruct, 3 seeds).

VariantBest verified path is a join (%)Mean log-probability gain over best sampled path (nats)Best-path updates that select a join (%)
No Composition0.0–0.0
Root-Only24.7+0.8421.6
Successful-Only16.8+0.6113.4
Full TROPIC31.6+1.1828.5

The gain is measured under the same frozen model, on problems where a join is the best verified path.

  • Root-Only: in 24.7% of solved problems, the best verified path is a join. The gain of 0.84 nats means it is about 2.3 times more likely than the best sampled solution. It is selected in 21.6% of best-path updates.
  • Full TROPIC: the share is 31.6%, the gain is 1.18 nats (about 3.3 times more likely), and joins are selected in 28.5% of best-path updates.

Composition therefore provides better training targets, not first solutions. This matches the success rates: Root-Only reaches 51.8% against 40.8% without composition, and removing composed paths at fixed acquisition costs 9.9 points (Table R1).


Thank you for your thoughtful feedback. We would appreciate it if you could let us know whether our clarifications address your concerns. If the responses above are sufficient, we kindly ask that you consider raising your score.

Reviewer_5kNDOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper argues that expected-return RL suits compositional reasoning poorly: summing over successful trajectories does not record which one succeeded, and under a normalized policy reinforcing one verified solution can lower another (Proposition 1). It replaces the sum with a max, giving a max-plus ("tropical") value, the log-probability of the best verified path, which splits at shared states into a best prefix and best suffix from different rollouts (Eq. 9). TROPIC keeps a per-problem graph of valid transitions, restarts from frontier states, composes and verifies joined paths, and trains by maximum likelihood on the archive. It has the best success rate in all eight task-by-model settings (Sokoban, Countdown, FrozenLake, WebShop; Qwen2.5-3B, Gemma 4 E4B), up to 16.2 points over SNR-Aware (Table 2).

Critical strengths

S1. The diagnosis is correct and useful. I checked the motivating example (Section 1) and Proposition 1: a verified solution can lose probability without being refuted, and max-plus composition (Eq. 9) is a simple, principled remedy.

S2. Composition is shown to do real work. On Sokoban, 31.6% of solved training problems were first solved by a composed path before any complete successful rollout (Table 3), and evaluation is a single attempt on 512 held-out instances with no archive or restarts (Appendix C), so the gains are in the trained policy. These two points are why I lean towards acceptance.

Critical weaknesses

W1 (main concern). The experiments that isolate composition cover one cell. The Table 2 baselines cannot restart or train on an archive, so Table 2 mixes restarts, archive-based maximum-likelihood training and composition. Appendix C calls TROPIC (No Composition) "closely related to archive-based exploration combined with rejection-sampling fine-tuning" (cf. Go-Explore, Ecoffet et al., 2021; ReSTEM\text{ReST}^{\text{EM}} , Singh et al., 2024, neither cited), yet it, MaxRL (51.3%) and GiGPO + T-STAR (53.1%) appear only on Sokoban with Qwen, where TROPIC's margin is 5.3 points rather than the 16.2 over SNR-Aware behind the abstract's "up to 16 percentage points". Since the claim is that the aggregation drives the gain, this comparison is the key evidence.

W2. The scope and the theory are stated more broadly than shown. The tasks are tiny (Sokoban 6×6 with one box, FrozenLake 4×4; Appendix B), where rollouts meet at shared states almost by construction, while the introduction motivates theorem proving and derivations. On theory, Proposition 1 is about the actor forgetting, while Lemma 3 is about the archive; Section 3.1 notes sum and LSE also satisfy Retention, so retention comes from keeping an archive, not from max. The Section 4.2 takeaway ("improving one solution never lowers any other") holds only for per-state logits, as the paragraph above it and Appendix D concede.

Questions for authors

Q1. Can you report TROPIC (No Composition), Root-Only and MaxRL for all four tasks and both models, in the Table 3 format? If composition explains most of the gap over No Composition across tasks, W1 is resolved and I would raise my score; if the gap disappears outside Sokoban, I would lower it. Q2. Per task, what fraction of archived paths are composed joins, and what fraction of training problems had at least one accepted join? Q3. Can you measure forgetting under shared parameters, e.g. the actor's log-likelihood of archived best paths on other problems across iterations? Q4. How is state identity defined in WebShop, and is it deterministic under replay?

Suggestions for future work (not affecting my score): 1: A larger state space where recurrence is not guaranteed (e.g. multi-box Sokoban). 2: Present Theorem 2 as a characterization (Section 4.1 notes it is Viterbi at λ = 1) and relate the method to trajectory stitching in offline RL. 3: Reword the Section 4.2 takeaway to match Appendix D, and qualify the training-time comparisons (e.g. "1.6 instead of 2.1 hours", Section 6), since each method uses its own stopping rule (Appendix C).

5 comments

Thank you for the review and for stating clearly what would change your assessment. We ran the requested ablations on all four tasks and both models. Composition explains the gain in every one of the eight settings.

W1 / Q1: Isolating composition in all settings

The three variants are:

  • No Composition keeps the archive, the frontier restarts, and likelihood training on archived paths, but never joins paths from different attempts.
  • Root-Only keeps composition but starts every attempt from the initial state, so it uses no restarts.
  • MaxRL is the maximum-likelihood RL objective, as in Table 3.

Table R5a. Success (%) on Qwen2.5-3B-Instruct (3 seeds).

MethodSokobanCountdownFrozenLakeWebShop
Best baseline of Table 242.228.977.258.8
MaxRL51.330.280.261.1
TROPIC (No Composition)40.828.178.859.1
TROPIC (Root-Only)51.831.583.162.4
Full TROPIC58.434.886.465.7

Table R5b. Success (%) on Gemma 4 E4B-it (3 seeds).

MethodSokobanCountdownFrozenLakeWebShop
Best baseline of Table 276.667.785.176.8
MaxRL78.969.587.477.1
TROPIC (No Composition)76.067.185.476.5
TROPIC (Root-Only)80.370.789.279.0
Full TROPIC83.173.692.381.4

So, the tables support four conclusions:

  • Restarts and archive training do not explain the gain. No Composition is within 1.6 points of the best Table 2 baseline in every setting.
  • Composition explains the gain. Adding it raises success by 4.9–17.6 points in every setting. In five of the eight settings, No Composition is below the best baseline, so composition accounts for the entire margin. In the other three, it accounts for more than 80% of it.
  • The gain does not depend on restarts. Root-Only starts every attempt from the initial state, as the baselines do. It still beats the best Table 2 baseline in all eight settings, by 2.2–9.6 points.
  • TROPIC is above MaxRL everywhere, by 4.1–7.1 points.

The gap does not disappear outside Sokoban. The smallest gain from composition is 4.9 points (WebShop, Gemma). We will include these ablations in the full Table 3 format in Appendix C.

Aggregation. Tables R5a and R5b show that composition supplies the solutions. Table R1 (response to Reviewer sof8) shows that the aggregation decides whether the model learns from them. There, every update rule is trained on the identical archive. The tropical update (Eq. 14) reaches 58.6% and MaxRL weighting 54.0%. Expected-return weighting reaches 39.7%, no better than No Composition. With the acquisition unchanged, removing composed paths from training costs 9.9 points (row A′).

Headline number. Both margins are in the submission. The abstract's "up to 16 points" refers to the on-policy baselines of Table 2, and Section 6.1 states the 5.3-point margin over GiGPO + T-STAR. We will report the two together.

Citations. We will cite Go-Explore (Ecoffet et al., 2021) and ReST-EM (Singh et al., 2024) in Section 5 and Appendix C.

Q2: How much composition occurs

A join is a verified solution built by joining a stored prefix from one attempt with a stored suffix from another. It was never sampled in one piece. Best-Join is the share of solved training problems whose best verified path is a join. The submission labeled this statistic First-Solve. We will rename it and correct its definition, because a join cannot be the first verified solution of a problem (Table R9, response to Reviewer bzED).

Table R6. Composition statistics during training (Qwen2.5-3B-Instruct, 3 seeds).

TaskArchived paths that are joins (%)Problems with an accepted join (%)Best-Join (%)
Sokoban38.671.931.6
Countdown26.855.519.3
FrozenLake30.261.717.5
WebShop18.939.812.4
  • Composition is frequent. Joins make up 18.9–38.6% of archived solutions, and 39.8–71.9% of training problems obtain at least one.
  • Joins become the training targets. For 12.4–31.6% of solved problems, the best verified path is a join. Without composition, the model would train on a less likely solution.
  • The gain follows the join frequency. Ordered by share of joins, the tasks are Sokoban, FrozenLake, Countdown, WebShop. The gain from composition in Table R5a follows the same order: 17.6, 7.6, 6.7, and 6.6 points.

We hope this resolves W1, as composition explains most of the gap across tasks. Tables R5a, R5b, and R6 show that it does in all eight settings.

W2: Scope

  • The tasks are the baselines' own benchmark. All four come from RAGEN-2 (Wang et al., 2026), the suite on which the strongest baseline, SNR-Aware, was introduced.
  • Shared states are measured, not guaranteed. A state includes the step count (Appendix B), so two attempts share a state only if they reach the same configuration at the same step. In WebShop, only 39.8% of problems ever obtain a join (Table R6).
  • Shared states can only help during training. At evaluation, TROPIC uses no archive, restarts, or composition. The model must solve 512 unseen instances in a single attempt, like the baselines (Appendix C).
  • The scope is stated. The abstract restricts TROPIC to deterministic, resettable environments with verifiable outcomes. Appendix C states that we do not claim generalization to a different distribution of compositions.

We will add that composition requires recurring intermediate states, with Table R6 as its measurement, and state that theorem proving is motivation and not an evaluated setting.

W2: Theory

Retention and the maximum. Section 3.1 states that addition and LSE satisfy Retention and fail Certification, and Theorem 2 requires both properties. Appendix D states that TROPIC guarantees that no verified computation is lost from memory, not that the actor never forgets. We therefore do not claim that retention alone singles out the maximum.

What the maximum adds to an archive is a concrete path, the witness, which can be replayed, joined, and trained on. An archive alone is not sufficient: in Table R1, expected-return weighting on the identical archive reaches 39.7%, against 58.6% for the tropical update. We will separate the roles of Lemma 3 (memory) and Proposition 1 (actor) explicitly in Section 3.1.

Section 4.2 takeaway. The restriction is stated in the main text, directly below Theorem 4: the theorem is exact for separate parameters per state and holds with shared parameters only up to interference. The takeaway box omits this qualifier. We will reword it to: "For an actor with separate parameters per state, an update on the best path cannot decrease the tropical value of any state in the retained graph. With shared parameters, interference can occur." Table R7 measures this interference.

Theorem 2. Section 4.1 already identifies the recursion as Viterbi decoding at λ=1\lambda = 1 and states that the new part is its use as a composing value and a learning rule.

Q3: Forgetting under shared parameters

We measured it directly:

  1. At iteration 50, we fix a probe set: the best archived path of every training problem that has a verified solution.
  2. At later checkpoints, we compute the probability that the current model assigns to each probe path.
  3. A path counts as deteriorated if its final probability is below half of its highest probability since iteration 50.

Each iteration trains on only 8 of the 128 training problems. A change on a probe path therefore comes mostly from updates on other problems.

Table R7. Likelihood of verified probe paths (Sokoban, Qwen2.5-3B-Instruct).

MethodChange in mean per-token log-likelihood (iteration 50 to final)Probe paths with ≥2× probability decrease (%)
TROPIC (best + coverage)+0.0786.8
TROPIC (best path only)+0.02815.4
GRPO−0.08430.2
  • Under TROPIC, verified paths become more likely on average (+0.078 per token), and 6.8% deteriorate.
  • Coverage paths more than halve the interference. Without them, 15.4% of probe paths deteriorate.
  • Under GRPO, the same paths become less likely on average (−0.084), and 30.2% deteriorate. This is consistent with Proposition 1.

Interference exists, but it is small and four times lower than under GRPO. We make no monotonicity claim for a shared-parameter model.

Q4: State identity in WebShop

  • Definition. Two attempts share a state if and only if the text observation given to the model (the current page and the selections made so far) and the step count are identical. The model conditions only on this observation. From a shared state, it has the same distribution over continuations, whichever attempt reached it. This is what Eq. 9 requires.
  • Determinism. The catalog and the search index are fixed, and transitions are deterministic under replay.
  • Safeguard. Identical observations could still hide a difference in the environment state. Every joined path is therefore re-executed from the initial state and accepted only if the verifier passes it (Sections 4.1 and 4.3). 98.1% of attempted WebShop joins pass. The rest are discarded before training.

Suggestions

  • Suggestion 2: Please see Theorem 2 above.
  • Suggestion 3: Please see the reworded takeaway above. For training times, Appendix C already states that each method uses its own stopping rule and that wall-clock time is not a matched-compute comparison. At matched model-token cost on Sokoban, TROPIC at half of its budget (45.8%) already exceeds SNR-Aware at the full budget (40.7%). See Table R4 in our response to reviewer sof8.
  • Suggestion 1: multi-box Sokoban is a natural next test. The join frequency in Table R6 is the quantity to track there.

Thank you for your thoughtful feedback. We would appreciate it if you could let us know whether our clarifications address your concerns. If the responses above are sufficient, we kindly ask that you consider raising your score.

Reviewer_sof8OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Tropical Reinforcement Learning, which defines value through the most likely verified successful path. Its TROPIC algorithm retains valid transitions from previous attempts, combines compatible path fragments, verifies the resulting solutions, and trains the policy on selected paths. Experiments on four deterministic, resettable tasks show improvements over the compared methods, with additional ablations examining composition and frontier exploration.

Critical strengths
  1. Reusing valid fragments from failed attempts is an interesting approach. The Sokoban ablation with Qwen2.5-3B-Instruct provides evidence for composition: removing it reduces success from 58.4% to 40.8%, while retaining memory and frontier restarts.

  2. The improvements are observed across four tasks and two models with three training seeds. Evaluation uses unseen instances and disables the archive and composition, showing that the benefits transfer to the trained policy.

Critical weaknesses
  1. The experiments support the usefulness of composition, but the contribution of changing the objective is less clear. Theorem 2 characterizes max under a requirement that the value select a path; it does not show that an expected-return learner cannot use a graph or composed solutions. The MaxRL and T-STAR comparisons also change the search and training pipeline. Section 5 discusses tree search and T-STAR; relating the archive-and-restart mechanism to Intelligent Go-Explore [1] would further clarify which elements are shared with prior exploration methods and which depend on the tropical objective.

  2. The description of the compute comparison is inconsistent. Figure 4 states that the methods use the same compute budget, whereas Appendix C describes different stopping rules and explicitly says the wall-clock comparison is not compute matched. The same number of rollout starts also does not account for differences in token generation, edge rescoring, and composition replays. The reported end-to-end times are useful, but success-versus-cost curves under a common budget would better support the efficiency claim.

[1] Lu C, Hu S, Clune J. Intelligent Go-Explore: Standing on the Shoulders of Giant Foundation Models[C]//International Conference on Learning Representations. 2025: 21276-21301.

Questions for authors
  1. Section 4.3 already trains on the best path and additional coverage paths. Can the authors compare the Eq. (14) update with an expected-return update while keeping data acquisition, the graph, composition, and the overall budget fixed?
  2. What happens when the graph reaches 1,024 edges or the archive reaches 64 solutions? If entries are evicted, how is the retained-capability guarantee affected?
  3. Does Figure 4 use the same runs and stopping rules as Table 2? Could the authors reconcile its caption with Appendix C and break down the rescoring, environment, and verification costs?
4 comments

hank you for the review. We ran the controlled experiment you proposed (Table R1). Please see the answers below.

W1 / Q1: Objective versus pipeline

Theorem 2 is not the result on which the paper bases its claim about expected-return learners. That claim rests on results that compare the two objectives on the same paths:

  • Proposition 3: expected return weights a verified path by its probability Pθ(τ∣x)P_\theta(\tau \mid x). The tropical gradient gives the witness, the most likely verified path, weight one.
  • Corollary 3: on a dd-step path with step probability ρ\rho, the expected-return gradient is of order ρd\rho^d. The tropical gradient is λ(1−π)\lambda(1-\pi), however unlikely the path.
  • Proposition 4(a): two instances with identical expected-return quantities can have different tropical greedy actions. No rule based on expected return can therefore select the tropical step.
  • Theorem 15 and Remark 2: with exact gradients on a chain, expected return needs a number of iterations exponential in dd, while the tropical value needs O(log⁡(1/ρ))O(\log(1/\rho)).

We will make this division explicit in Sections 1 and 3.1.

Composition also depends on the objective. TROPIC joins the best prefixes and suffixes at a shared state and replays the joined paths, which requires a value that names concrete paths. A sum reports the total success through a state, not which prefix and suffix produced it (Observation 1). The maximum names them (Eq. 9).

Controlled experiment. We saved the graph and archive of every problem at every iteration of the TROPIC runs. We then trained each update rule on this identical stream, with the same initialization, optimizer, and number of updates, and a matched training-token budget (last column). Only the choice and weighting of paths differ. A composed path is a verified path that exists in the archive only through composition: it was assembled from parts of different attempts and not sampled in one piece. The third column is the share of update weight on such paths.

Table R1. Update rules trained on the same data (Sokoban, Qwen2.5-3B-Instruct, 3 seeds).

Update ruleSuccess (%)Weight on composed paths (%)Trained tokens per step (k)
A. Tropical, Eq. 14 (witness + coverage paths, unit weights)58.6 ± 1.839.86.4
A′. As A, with composed paths excluded from training48.7 ± 2.0–6.2
B. Tropical, witness only55.6 ± 1.947.16.3
C. Uniform over distinct archived paths (≈ rejection-sampling FT)51.9 ± 2.326.26.6
D. Probability normalized per problem (MaxRL weighting)54.0 ± 1.814.26.5
E. Raw probability Pθ(τ∣x)P_\theta(\tau \mid x) (expected return)39.7 ± 2.03.56.4

Expected return (E vs. A). Row E has the same composed solutions available as row A, yet it reaches 39.7%. That is no better than the No Composition ablation (40.8%), which never builds composed solutions. Composed paths were never generated in one piece, so they have low probability, and row E puts only 3.5% of its weight on them. As Proposition 3 and Corollary 3 predict, the same data is worth 18.9 points under Eq. 14 and almost nothing under expected return.

Composed paths as training targets (A′ vs. A). Removing composed paths from training, with the acquisition unchanged, costs 9.9 points. Tropical training without them (48.7%) still beats expected return with them (39.7%).

Would a baseline or critic change row E? No. Row E is the exact expected-return gradient over the archived verified paths (Proposition 3), not a sampled estimate, so a baseline or critic has no variance to reduce. On verified paths, a baseline rescales all weights equally, so the 3.5% share is unchanged. This is the point of Remark 2. The variance-reduced learners are also in Table 2 (PPO and SNR-Aware with a critic, GRPO and DAPO with group baselines). None exceeds 42.2% on Sokoban.

MaxRL (D vs. A). With the pipeline fixed, row D reaches 54.0%, which is 4.6 points below Eq. 14. Normalizing per problem keeps rarely solved problems from being ignored, which is why D far outperforms E. Within each problem, likely paths still dominate, and only 14.2% of D's weight reaches composed paths. The witness-only variant (row B, 55.6%) is already above D.

The same ordering holds on Countdown (A: 34.9%, E: 27.6%) and when each rule collects its own data (Sokoban, A: 58.2%, E: 37.9%). The fixed stream therefore does not favor TROPIC.

T-STAR. T-STAR is built on GiGPO and keeps the expected-return objective. Its grafting changes how credit is assigned, not how alternative paths are weighted. Section 5 already notes that T-STAR reuses sampled trajectories, whereas TROPIC composes solutions never sampled in one piece. With the data fixed, row E is the closest analogue of its objective.

Go-Explore and IGE

We will add IGE to the discussion in Section 5. IGE asks a foundation model to judge which states and actions are worth pursuing. The foundation model itself is not trained. The component TROPIC shares with Go-Explore and IGE is keeping an archive and restarting from archived states. Table 3 already isolates it:

  • No Composition keeps the archive and the restarts. It reaches 40.8%, on par with the strongest Table 2 baseline.
  • Root-Only drops the restarts but keeps composition. It reaches 51.8%, above every Table 2 baseline.

Both findings hold in all eight task and model settings (Tables R5a and R5b, response to Reviewer 5kND).

What TROPIC adds is different in kind. Go-Explore and IGE extend an archived prefix by exploring forward from it. Neither joins an archived prefix to a suffix that a separate attempt has already found from the same state. TROPIC does this, including for suffixes from failed attempts. It then verifies every joined solution and trains on it with an update that does not discount it for being improbable.

W2 / Q3: Compute

Figure 4 uses the same runs, seeds, and stopping rules as Table 2. Its caption should read "same rollout budget", and we will correct it. The rest of the paper was consistent on this point. Appendix C states that the 16 rollout starts "do not imply equal generated-token counts or verification costs." It also states that replay generates no tokens and that wall-clock times are not a matched-compute comparison.

Cost breakdown:

  • Generation: 0.84× GRPO's tokens per iteration, since attempts started from frontier states generate only suffixes.
  • Rescoring: a forward pass only, over at most 1,024 stored steps per problem, with eight problems per iteration.
  • Composition replay: environment and verifier calls only, at most 128 per active problem per iteration.
  • Rescoring and replay combined: 11.6% of total training time.

We will include the full per-iteration breakdown in Appendix C.

Table R4 reports validation success at matched cumulative model-token cost, counting generation, rescoring, and optimization. Each column is a fraction of TROPIC's total cost.

Table R4. Validation success (%) at matched model-token cost (Sokoban, Qwen2.5-3B-Instruct).

Method25%50%75%100%
GRPO18.724.025.926.8
SNR-Aware26.334.438.340.7
TROPIC25.245.853.758.1

From 50% onward, TROPIC leads at every budget. At 50% of the budget it already exceeds SNR-Aware at 100% (45.8% vs. 40.7%). At 100% the gap is 17.4 points. All methods are compared at equal cost, so this result does not depend on stopping rules.

Costs outside the token count. Table R4 counts rescoring but not composition replay, which uses only environment and verifier calls. Replay is part of the 11.6% above. A cost of this size cannot explain the gap: TROPIC at 75% of the budget is 13.0 points above SNR-Aware at 100%.

End-to-end wall-clock time includes every environment and verifier call, and it points the same way. In Table 2, TROPIC's complete Sokoban run takes 1.60 h and ends at 58.4%. SNR-Aware takes 2.10 h for 42.2%, and GRPO takes 2.90 h for 27.6%. Matching wall-clock time at TROPIC's budget would therefore stop the baselines earlier than their own protocol does.

Q2: Capacity

Neither limit removes a verified solution, so Lemma 3 holds. Lemma 3 only requires that the certified subgraph, meaning the set of steps that lie on at least one verified path, never shrinks.

  • Graph limit (1,024 steps): only steps on no verified path are evicted, hardest-to-reach first. If verified steps alone fill the capacity, new candidates are rejected. The full graph may violate Et⊆Et+1E_t \subseteq E_{t+1}, but the certified subgraph only grows, and Vcap[t]V_{\text{cap}}[t] is a maximum over verified solutions within it.
  • Archive limit (64 solutions): the lowest-scoring non-witness solution may be dropped, but its steps stay in the graph, and the dynamic program can rebuild it.

Capacity can slow exploration, but it cannot erase verified solutions. Two facts limit its practical effect:

  • Rejection hits the problems that need it least. Candidates are rejected only when verified steps alone fill the capacity. Such a problem already has many verified solutions, while training uses at most two paths per problem per iteration (K=2K = 2).
  • The reported numbers already include it. All results in Tables 2, 3, R1, and R4 were obtained with both limits active, so any cost of capacity is already reflected in them.

We will add a remark after Lemma 3 stating this.


Thank you for your thoughtful feedback. We would appreciate it if you could let us know whether our clarifications address your concerns. If the responses above are sufficient, we kindly ask that you consider raising your score.

AuthorsOpenReview ↗

Kind reminder

Dear Reviewer sof8,

Just a brief reminder that the author-reviewer discussion period concludes in a few days.

In our response, we ran the controlled experiment you proposed: every update rule was trained on the identical archive with a matched budget (Table R1). The tropical update reaches 58.6%, MaxRL weighting 54.0%, and expected-return weighting 39.7%, so the objective matters beyond the pipeline. We also corrected the Figure 4 caption and reported success at matched token cost (Table R4). At half of its budget, TROPIC (45.8%) already exceeds SNR-Aware at the full budget (40.7%).

If these responses address your concerns, we would appreciate it if you could acknowledge this and consider reassessing your rating. We are happy to answer any follow-up questions.

Best regards, Authors

Thank you for running the controlled experiments. The comparison using the same graph and archive stream substantially addresses my concern about separating the objective from data acquisition. The token-cost curves and the clarification of Figure 4 also address much of my concern about the efficiency comparison. These results make my assessment more positive.

I interpret the corrected Best-Join statistic as evidence that composition provides better training targets after a solution has been found, rather than evidence that joins discover the first solution. I also view the expected-return comparison as evidence about the archive-based objectives evaluated, and the token-cost result as distinct from end-to-end cost including replay and verification. With these qualifications, my original concerns are substantially reduced.

The controlled results provide sufficient support for the contribution within this scope. I now lean toward weak acceptance (rating 3).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.