PaperlayerView exact revision on arXiv

Source-linked AI summary

Tropical Reinforcement Learning

Arip Asadulaev, Aladin Djuhera, Karim Salta, Holger Boche, Fakhri Karray, Martin Takac

arXiv:2610.02478v1cs.AI

TL;DR

Expected return sums successful trajectories but can miss solutions assembled from fragments found in separate attempts. Tropical RL replaces that sum with a maximum over verified paths, and TROPIC outperforms the strongest on-policy baselines across four agentic tasks by up to 16 points.

  • Problem

    Expected return requires a solution to be sampled end-to-end and can suppress individual fragments needed for a future composition.

    Source: §1 · p. 1, §3 · p. 3

  • Method

    Tropical RL replaces summation over alternatives with maximum aggregation, retaining a verified path as the value and enabling path composition.

    Source: §3.1 · p. 4

  • Results

    TROPIC outperforms all baselines on every tested task and model, by up to 16 points over the strongest one.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The tropical value names a concrete verified path, retains it once found, and splits at a shared state into a best prefix and suffix for assembly.

    Source: §7 · p. 9

    With shared parameters, as in a language model, the compositional policy-improvement guarantee holds only up to interference from updates at other states.

    Source: §4.2 · p. 6

Abstract

from arXiv · show

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

1 INTRODUCTION

Expected return requires a complete solution to be sampled and can suppress fragments needed for future compositions. Tropical RL instead takes the maximum over alternative trajectories, retaining a verifiable path that can be joined across rollouts; TROPIC applies this approach to agentic tasks.

1 INTRODUCTION

  • A solution chaining d fragments found in separate attempts has exponentially small probability of being sampled in one piece, despite every fragment having appeared before.The expected-return formulation credits a trajectory only after the policy generates it end-to-end.Source: §1 · p. 1
  • Expected return can suppress a needed fragment: reward rises from 0.60 to 0.95 while B's chance of appearing in a batch of twenty rollouts falls from approximately 0.999 to 0.642.A high expected reward gives no lower bound on the probability of any individual fragment required by a future composition.Source: §1 · pp. 1–2
  • Tropical RL combines alternative trajectories by their maximum, making a state's value the log-probability of its most likely verified path, which can be split at a shared state into a best prefix and suffix.The two fragments may come from different rollouts, so their composition need not have been sampled as a whole.Source: §1 · p. 2
  • TROPIC outperforms all baselines on every tested task and model, by up to 16 points over the strongest baseline.The paper identifies Sokoban, Countdown, FrozenLake, and WebShop as evaluation tasks.Source: §1 · p. 2
  • The introduction frames the contributions as a diagnosis of expected return, a forcing result for maximum aggregation, and TROPIC, which joins fragments across rollouts.The paper reports that the maximum is the only aggregation whose value always names a verified path and never decreases as paths are found.Source: §1 · p. 2

2 PRELIMINARIES

The preliminaries define a reasoning problem as a state-transition process and distinguish verified continuations from unsuccessful ones. They define compositional generalization around recombining known fragments in a solution not previously observed as a whole, and give expected value an operational interpretation as sampled success probability.

2 PRELIMINARIES

  • A problem x is represented by states as computational interfaces, actions as steps that produce next states, and trajectories whose probabilities are evaluated under a frozen model.A terminal verifier assigns a binary acceptance value to a complete response.Source: §2 · p. 2
  • Compositional generalization means solving problems with known fragments combined in a way not observed in one rollout, even if every fragment appeared in some separate attempt.A solution is compositional when it sequences reusable computations, each beginning at the state produced by the previous one.Source: §2 · p. 2
  • In a deterministic computation graph, expected value is the probability that one continuation sampled from the policy will eventually pass the verifier.The Bellman formulation multiplies probabilities of successive steps and adds probabilities of alternative actions.Source: §2 · p. 2
  • Figure 2 contrasts expected V with maximum M for continuations.The supplied caption identifies the comparison as a difference between expected V and max M continuation.Source: Figure 2 · p. 3

3 THE ALGEBRA OF EXPECTED RETURN

Expected-return addition aggregates success probabilities but does not identify which verified path worked, and policy updates can reduce the probability of an unseen verified action. Tropical RL keeps additive log-scores along paths but uses a maximum across alternatives, yielding a value tied to a concrete verified path.

3 THE ALGEBRA OF EXPECTED RETURN

  • Expected-return addition is nonselective, normalized, and non-idempotent, so it aggregates success rather than naming a path and favors computations found more often.The sum can also lower the probability of another alternative because action probabilities are normalized.Source: §3 · p. 3
  • A policy-gradient update can lower the value of an unseen verified action after reinforcing a sampled successful action.The proof shows that restoring the unseen action's probability requires sampling it again.Source: §3 · p. 3

3.1 REPLACING THE AGGREGATION

  • Tropical RL keeps additive log-scores along paths but replaces alternative aggregation with a maximum, making the state value the score of a verified path.Certification and retention force the maximum, yielding the max-plus or tropical semiring.Source: §3.1 · p. 4
  • The tropical value is the score of the best verified continuation, interpreted as the distance from the actor to its nearest verified computation.The cited passage states that Section 4 builds reinforcement learning on this value.Source: §3.1 · p. 4
  • With a fixed verifier and retained discoveries, capability cannot decrease as the transition graph grows.The maximum over a growing set of verified continuations is monotone.Source: §3.1 · p. 4
  • Distributivity lets the best prefix and suffix meeting at a shared state be chosen independently, enabling dynamic programming over many compositions.The two fragments can come from different rollouts, and composed paths can be scored without resampling.Source: §3 · p. 3, §3.1 · p. 4

4 TROPICAL REINFORCEMENT LEARNING

Tropical RL replaces the sum over alternative trajectories with a maximum, so a state’s value identifies its best verified path. TROPIC uses retained paths and cross-rollout composition to train on solutions assembled from fragments.

4.1 TROPICAL BELLMAN EQUATIONS

  • The tropical Bellman recursion takes the best action value, yielding the score of the best path; with a binary verifier, rejected paths drop out.At λ = 1 it is Viterbi decoding under the frozen model restricted to verified paths.Source: §4.1 · p. 5

4.2 IMPROVEMENT COMPOSES

  • Training on a best verified path raises tropical values at states whose best paths pass through it, including states not trained from, with shared-parameter interference qualifying the guarantee.A joined best path can inherit the gain on its suffix; the theorem is exact for separate per-state parameters.Source: §4.2 · p. 6
  • Tropical gradients give unit weight to a verified path even when its problem is rarely solved, while the archive supplies paths the actor seldom finds alone.Raising tropical value raises a lower bound on pass@1 and pass@k, but does not by itself force pass@1 to increase.Source: §4.2 · p. 6

4.3 TROPIC: TROPICAL POLICY OPTIMIZATION

  • TROPIC joins known prefixes and suffixes at shared states, replays and verifies the resulting paths, and can find solutions never sampled in one piece.Its graph retains valid steps from failed attempts as well as verified complete paths.Source: §4.3 · pp. 6–7
  • TROPIC selects archived paths for likelihood training, including additional paths chosen to rehearse rarely trained steps rather than push paths down.The objective has no reward weights or baseline.Source: §4.3 · p. 7

5 RELATED WORK

Prior RL post-training methods largely retain expected return, while other approaches optimize pass@k or modify how trajectories are reused. This work differs by changing how alternative trajectories are aggregated.

5 RELATED WORK

  • Methods such as DAPO, SNR-aware filtering, GiGPO, and process supervision refine training or credit assignment but optimize expected return, requiring a composition to be sampled in one piece before reinforcement.These approaches are presented as complementary to changing trajectory aggregation.Source: §5 · p. 7
  • MaxRL takes the logarithm of the sum of verified-path probabilities, whereas Tropical RL takes their maximum, selecting an alternative rather than summing alternatives.Other cited approaches optimize pass@k directly.Source: §5 · pp. 7–8
  • Tree search and methods such as T-STAR reuse sampled trajectories, while TROPIC also composes verified solutions never sampled in one piece.Prior max-plus methods address value functions of deterministic control problems; this work uses max-plus to define a language-model policy’s learning objective.Source: §5 · p. 8

6 EXPERIMENTS AND RESULTS

Across four interactive tasks and two model families, TROPIC has the highest reported success rate in every setting. Ablations indicate that cross-rollout composition is its main source of improvement, with frontier restarts and failed-rollout fragments also contributing.

6 EXPERIMENTS AND RESULTS

  • TROPIC has the highest success rate on every task for both models; it trains faster in all but one setting while generating comparable or fewer tokens.On Sokoban, it beats SNR-Aware by 16.2 points with Qwen and 6.6 points with Gemma; Qwen training takes 1.6 rather than 2.1 hours.Source: §6 · pp. 8–9

6.1 ABLATION RESULTS

  • Disabling composition reduces Qwen Sokoban success from 58.4% to 40.8%, versus 42.2% for SNR-Aware, the largest ablation drop.Root-Only reaches 51.8% success and reduces First-Solve from 31.6% to 24.7%; Successful-Only reaches 53.3%.Source: §6.1 · p. 9
  • TROPIC reaches 58.4% on Qwen Sokoban, 5.3 points above the strongest alternative-method comparison, with the fewest tokens and shortest training time.The compared success rates are 51.3% for MaxRL, 47.6% for GiGPO, and 53.1% for T-STAR.Source: §6.1 · p. 9

7 CONCLUSION AND DISCUSSION

TROPIC uses tropical values to retain verified paths and compose solutions from fragments found in separate rollouts. It outperforms the strongest on-policy baselines on every tested task and model.

7 CONCLUSION AND DISCUSSION

  • Table 3 covers Sokoban with Qwen2.5-3B-Instruct, reporting success rate, tokens per episode, training time, and First-Solve.Source: Table 3 · p. 9
  • TROPIC outperforms the strongest on-policy baselines on every task and model tested.The conclusion identifies transferring the growing set of verified computations into model weights as a natural next step.Source: §7 · p. 9
  • A tropical value names a concrete verified path, never loses a discovered path, and supports joining best prefixes and suffixes at shared states.The joined fragments need not have been sampled together.Source: §7 · p. 9

REPRODUCIBILITY STATEMENT

The statement directs readers to appendices for experimental details and formal proofs, and discloses how generative AI tools were used and reviewed.

REPRODUCIBILITY STATEMENT

  • Appendix B specifies the environments, metric definitions, and training procedure, while Appendix C reports compute use.Source: REPRODUCIBILITY STATEMENT · p. 10
  • The authors state that assumptions behind theoretical claims are in Appendix A and that its propositions are proved there.Source: REPRODUCIBILITY STATEMENT · p. 10
  • Generative AI tools assisted with writing, code, and parts of theoretical analysis; the authors say they reviewed the assisted work and retain responsibility.They state that AI was not used for retrieval and discovery and that the research ideas and core analysis are original.Source: AI USE STATEMENT · p. 10

A STRUCTURAL RESULTS AND PROOFS

The appendix develops structural results around verified computations and specifies the finite acyclic computation-graph setting used for them.

A STRUCTURAL RESULTS AND PROOFS

  • The appendix develops results on objective geometry, frequency-free learning signals, policy improvement, and tropical policy gradients.It also gives an exponential-versus-logarithmic separation between expected-return and tropical gradient ascent on a chain.Source: A STRUCTURAL RESULTS AND PROOFS · p. 15
  • The tropical value aggregates a set of verified computations by maximum, while expected return aggregates a measure over them by sum.The appendix attributes the distinction to maximum being idempotent, attained by one argument, and insensitive to nonmaximal arguments.Source: A STRUCTURAL RESULTS AND PROOFS · p. 15

A.1 SETTING AND CONVENTIONS

  • The analysis assumes a finite acyclic computation graph with finite action sets and deterministic transitions.Paths visit each state at most once; the retained graph contains states and edges visited by certified paths.Source: §A.1 · p. 15
  • Path scores add log-policy accessibility and internal reward, with terminal scores; the main structural sections use unit accessibility, zero internal reward, and a binary boundary.Source: §A.1 · p. 15

A.2 THREE PROJECTIONS ONTO THE CERTIFIED SET

The appendix interprets learning objectives as distances to certified computations and shows why maximum aggregation supports both path certification and frequency-free learning.

A.2 THREE PROJECTIONS ONTO THE CERTIFIED SET

  • The three objectives correspond to distances from the actor’s path distribution to the certified simplex, its posterior distribution, or its nearest certified path.The tropical value measures distance to a computation, rather than to a distribution over computations.Source: §A.2 · p. 16
  • Continuity, certification, and retention force maximum aggregation, whose value is the score of an actual certified path.The theorem identifies the tropical value with the negative KL distance to the nearest certified vertex.Source: §A.2 · p. 17
  • Maximum aggregation gives optimal substructure: the best suffix of an optimal path is itself optimal, and best prefixes and suffixes can be combined at a shared state.A maximizing path can also be replayed and checked with one verifier call.Source: §A.2 · p. 18

A.3 FREQUENCY-FREE LEARNING SIGNALS

  • An aggregation is frequency-free exactly when it is idempotent; maximum has this property, whereas log-sum-exp and addition do not.Source: §A.3 · pp. 18–19
  • Expected-return gradients weight paths by their probabilities, maximum-likelihood gradients by a posterior, and tropical gradients by an indicator of the maximizing path.Duplicating a retained path changes the first two objectives’ weights but leaves the tropical gradient unchanged when the maximizer is unique.Source: §A.3 · p. 19
  • Because the tropical signal depends on which computations are found, not how often, TROPIC can acquire paths off-policy without importance weights.Its coverage counter tracks rehearsals chosen by the algorithm rather than actor-generated samples.Source: §A.3 · p. 19

A.4 COMPOSITIONAL POLICY IMPROVEMENT

This section develops compositional policy improvement in tropical learning, describing how a greedy-path update propagates gains through certified graphs and shared interfaces and how TROPIC composes and retains certified computations. It also examines chain behavior, including the theorem’s rate separation between expected return and its logarithm and tropical learning’s use of one nearest certified computation.

A.4 COMPOSITIONAL POLICY IMPROVEMENT

  • The update is a K = 1 maximum-likelihood step on a certified greedy path; maximum-based substructure, join, and blindness support its compositional improvement guarantee.The greedy path’s suffix from any visited state is itself that state’s greedy path, and the greedy action gains more in log units than any alternative at a trained state.Source: §A.4 · pp. 19–21
  • One tropical greedy-path update gives pointwise non-decreasing values across the certified graph, adds gains over shared fragments, and passes the full suffix gain to shared interfaces.Repeated updates preserve the trained path and produce non-decreasing values at every state.Source: §A.4 · p. 22
  • Expected-return information cannot always identify the tropical greedy action, and increasing either the tropical- or expected-return-greedy action can lower the other value.The proposition shows that the two improvement criteria can be mutually harmful.Source: §A.4 · p. 22
  • The coverage-path update may sacrifice local monotonicity when it takes a non-greedy action at a state shared with the first path, trading accessibility for fragment rehearsal.The theorem’s strict monotonicity need not hold at that shared state.Source: §A.4 · p. 23

A.5 THE TROPICAL PERFORMANCE DIFFERENCE LEMMA

  • The tropical performance difference lemma replaces an expectation over new-policy trajectories with a single-path sum and an additive log-ratio of the two actors.The log-ratio appears because the actor’s log-likelihood is part of the per-step reward.Source: §A.5 · pp. 23–24
  • For any certified path, its deficit from the tropical value equals the sum of its tropical advantages; a maximizing witness has zero deficit, so no advantage estimate is needed.The advantages are local quantities computable by dynamic programming.Source: §A.5 · p. 24
  • The new witness’s log-likelihood gain is a penalty-free lower bound on true improvement, and the witness itself is the concrete slack contributed by composition.When discovery or composition makes a new path optimal under the new actor, that path accounts for the slack.Source: §A.5 · p. 24
  • Classical gradients on a path with step probabilities ρ are of order ρ^d, whereas the tropical gradient on its certified witness is order one.Natural policy gradient removes the upstream reachability factor but retains the completion factor; tropical gradient removes both.Source: §A.5 · p. 25
  • On a chain, bound (a) is exponential in depth d, whereas bound (b) is logarithmic in 1/ρ and independent of d, followed by a 1/n rate.Source: §A.5 · p. 25
  • On a single certified path, the tropical value equals log expected return, but with multiple paths tropical ascent follows one path while maximum-likelihood gradients distribute weight across them.The theorem’s rate separation is between expected return and its logarithm, and its exponential cost is an objective-landscape property rather than a sampling artifact.Source: §A.5 · p. 26

A.6 HOW TROPIC REALIZES THESE RESULTS

  • TROPIC adds discovered and composed certified vertices to a nonshrinking archive, rescoring them under the frozen actor before maximum-likelihood improvement on the nearest vertex.Separate prefix and suffix passes can be joined; acquisition can be off-policy without correction, and the update improves the retained graph pointwise.Source: §A.6 · p. 26

B RL ENVIRONMENTS

The four deterministic, terminally verified tasks share states across attempts, giving TROPIC interfaces for joining partial paths that expected-return methods cannot credit until a full episode succeeds. Their state representations and failure modes vary by environment.

B RL ENVIRONMENTS

  • In Sokoban, different move orders often reach the same board, so a successful suffix can complete another attempt’s correct but unsuccessful pushes.A state is the agent and box positions; pushing into a wall or corner can make the puzzle unsolvable.Source: B RL ENVIRONMENTS · p. 27
  • In Countdown, disjoint arithmetic steps can reach the same remaining-number multiset, allowing a useful intermediate result to join a successful derivation.The verifier checks whether the final number equals the target, with each input number used exactly once.Source: B RL ENVIRONMENTS · p. 27
  • In FrozenLake, a single misstep ends an episode, but TROPIC can retain safe prefixes and complete a route from another attempt’s frontier.Transitions are deterministic in the experiments, although each cell is safe with probability 0.9 when the map is generated.Source: B RL ENVIRONMENTS · p. 27
  • In WebShop, a correct search and navigation sequence can join a correct selection-and-purchase suffix from the same product page.A state records the current page and selections; success requires purchasing an item that satisfies all requested attributes.Source: B RL ENVIRONMENTS · pp. 27–28
  • Sparse terminal rewards and repeated intermediate states let TROPIC retain valid steps from failed attempts and assemble verified solutions where attempts meet.On-policy baselines must sample a complete successful episode before reinforcing its steps.Source: B RL ENVIRONMENTS · pp. 27–28

C TRAINING AND EVALUATION SETUP

The setup compares TROPIC with established on-policy methods across two model families, using shared rollout budgets and held-out single-attempt evaluation. It also specifies training, evaluation metrics, and protocol differences relevant to interpreting the comparisons.

C TRAINING AND EVALUATION SETUP

  • The study fine-tunes Qwen2.5-3B-Instruct and Gemma-4-E4B-it and compares PPO, GRPO, DAPO, and SNR-Aware Filtering, alongside additional methods in Table 3.All policies are fully fine-tuned without parameter-efficient adapters.Source: C TRAINING AND EVALUATION SETUP · p. 28
  • TROPIC makes maximum-likelihood updates on verified paths, retaining valid transitions from failed attempts while training only on complete paths replayed and verifier-accepted from the initial state.It uses 16 rollout starts per problem per iteration; graph memory persists across a recurring pool of 128 training problems, with eight visited per iteration.Source: C TRAINING AND EVALUATION SETUP · p. 28
  • Experiments use eight NVIDIA A100 GPUs with FSDP and BF16; training is capped at 200 iterations for three tasks and 100 for WebShop.Validation occurs before training and every 25 iterations.Source: C TRAINING AND EVALUATION SETUP · pp. 28–29
  • Evaluation uses 512 held-out instances per environment and single-attempt decoding; reported outcomes include success rate, pass@k, generated tokens, training wall-clock time, and FIRST-SOLVE in ablations.Results are means and standard deviations across three independent training seeds; TROPIC uses no archive, restarts, or composition at evaluation.Source: C TRAINING AND EVALUATION SETUP · p. 29
  • On Sokoban, 31.6% of solved training problems are first solved by a composition never sampled end to end; held-out success tests new instances, not systematic generalization across composition distributions.At evaluation, the policy must solve unseen instances without TROPIC’s search machinery.Source: C TRAINING AND EVALUATION SETUP · p. 29
  • The comparison includes frontier restarts, composed-path replay and verification, and TROPIC’s own stopping rule; replay adds environment calls but no generated tokens.Wall-clock times reflect each method’s standard protocol, not matched compute; all methods use the same iteration cap and evaluate final checkpoints on the same held-out instances.Source: C TRAINING AND EVALUATION SETUP · p. 30
  • TROPIC (Root-Only) reaches 51.8% on Sokoban, above every baseline; TROPIC (No Composition) reaches 40.8% versus SNR-Aware at 42.2%.The ablation comparison attributes the improvement to composing fragments across attempts, not to frontier restarts.Source: C TRAINING AND EVALUATION SETUP · p. 30

D LIMITATIONS

TROPIC preserves verified computations in memory, but does not guarantee that a language model will retain them; transferring this record into shared weights without interference remains open.

D LIMITATIONS

  • On four agentic tasks, Tropical RL yields higher single-attempt success than on-policy baselines by assembling fragments the actor did not produce together.The state value splits into a best prefix and suffix at a shared state.Source: D LIMITATIONS · p. 30
  • TROPIC guarantees that verified computations remain in memory, but shared parameters can still reduce the likelihood of a verified path on another problem.Coverage paths mitigate this risk but are a heuristic, not a proof.Source: D LIMITATIONS · p. 30
  • Whether the growing record of verified computations can be transferred into shared weights without interference at scale remains open.The paper identifies continual self-improvement as a promising direction, with verified capabilities retained and reused by later ones.Source: D LIMITATIONS · p. 30

Related papers

Loading 2610.02478v1…