热带强化学习

# Tropical Reinforcement Learning
Source: [https://arxiv.org/html/2610.02478](https://arxiv.org/html/2610.02478)
###### 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 introduceTropic, a training algorithm for deterministic, resettable environments with verifiable outcomes\. On four agentic tasks \(Sokoban, Countdown, FrozenLake, WebShop\),Tropicoutperforms 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\.

††footnotetext:arip\.asadulaev@mbzuai\.ac\.ae†MBZUAI‡TUM## 1Introduction

![Refer to caption](https://arxiv.org/html/2610.02478v1/Images/sokoban_passk_3.png)Figure 1:*Sokoban pass@k results*The best solution a language model can produce is often one it has never produced\. A model may know how to formalize a problem, derive an intermediate result, invoke the right theorem, and check an answer, and may have done each of these in earlier attempts, yet never have chained them in the order a new problem requires\([Press et al\., 2023](https://arxiv.org/html/2610.02478#bib.bib46);[Lake and Baroni, 2018](https://arxiv.org/html/2610.02478#bib.bib44)\)\. Reinforcement learning with verifiable rewards \(RLVR\) is the standard post\-training tool for closing this gap by sampling many attempts and reinforcing the ones a verifier accepts\([Kimi Team et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib37);[DeepSeek\-AI and others, 2026](https://arxiv.org/html/2610.02478#bib.bib23);[GLM\-5\-Team and others, 2026](https://arxiv.org/html/2610.02478#bib.bib20);[Yuan et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib39);[Wen et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib40)\)\. However, the classical expected\-return formulation learns only from what it samples, as a trajectory is credited only after the policy has generated it end\-to\-end\. Recent works therefore focus on trajectory design, improving which rollouts are sampled and how they are credited\([Wang et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib11);[Feng et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib12);[Li et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib24)\)\. Yet these methods keep the expected\-return objective, and with it the requirement that a solution be sampled in one piece\. For composition, this requirement is the bottleneck: a solution that chainsddfragments, each found in a separate attempt, is sampled in one piece with probability exponentially small indd, even though the model has already produced every part of it\.

Beyond failing to reward composition, expected return can also actively suppress the fragments it requires\. Suppose the model produces outcomesAA,BB, their compositionA∘BA\\circ B, and a failure00, with probabilities\(pA,pB,pA​B,p0\)\(p\_\{A\},p\_\{B\},p\_\{AB\},p\_\{0\}\)\. The first three receive reward one, soJER=pA\+pB\+pA​BJ\_\{\\mathrm\{ER\}\}=p\_\{A\}\+p\_\{B\}\+p\_\{AB\}, but the composition has not yet been sampled\. Moving from\(0\.30,0\.30,0,0\.40\)\(0\.30,0\.30,0,0\.40\)to\(0\.90,0\.05,0,0\.05\)\(0\.90,0\.05,0,0\.05\)raises expected reward from0\.600\.60to0\.950\.95\. Yet the probability that a batch of twenty rollouts containsBBat least once drops from1−0\.7020≈0\.9991\-0\.70^\{20\}\\approx 0\.999to1−0\.9520≈0\.6421\-0\.95^\{20\}\\approx 0\.642\. The objective has improved, but one of the two fragments thatA∘BA\\circ Brequires is now absent from about a third of all batches\. In general, a high expected reward bounds the*total*probability of currently successful behavior, but places no lower bound on any*individual*fragment that a future composition requires\. This is consistent with recent findings that loss of policy entropy and reasoning diversity limits what RL post\-training can achieve\([Cui et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib21);[Jin et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib22)\)\.

Both problems stem from the same choice: expected return*adds up*the probabilities of alternative trajectories\. A sum does not record which trajectory succeeded, so fragments from different rollouts cannot be combined, and, because probabilities sum to one, raising one term lowers another\. Tropical RL changes this algebra\. It still adds log\-probabilities*along*each trajectory, but combines alternative trajectories by their*maximum*, which yields the max\-plus, or*tropical*, semiring\. The value of a state becomes the log\-probability of its most likely verified path, and, because addition distributes over the maximum, it splits at any shared state into a best prefix and a best suffix, possibly from different rollouts\. Compositions can thus be assembled without ever being sampled in one piece, and since the maximum ignores all but the best path, the value never loses a verified path once found\. RL thus shifts from learning what the policy samples to learning what can be assembled from it\.

We develop this shift from first principles to a practical algorithm\. Our contributions are: \(i\) adiagnosis: we show that expected return, by adding probabilities over alternative trajectories, loses track of which solution succeeded and lets verified solutions be forgotten \(Section[3](https://arxiv.org/html/2610.02478#S3)\); \(ii\) aforcing result: we prove that the maximum is the only aggregation whose value always names a verified path and never decreases as new paths are found \(Theorem[2](https://arxiv.org/html/2610.02478#Thmtheorem2)\); and \(iii\)Tropic: an algorithm of Tropical RL for agentic environments that joins fragments across rollouts and outperforms all baselines \(Fig\.[4](https://arxiv.org/html/2610.02478#S4.F4), Fig\.[1](https://arxiv.org/html/2610.02478#S1.F1)\) on every task and model we test, by up to 16 points over the strongest one\.

## 2Preliminaries

Notations\.Letxxdenote a reasoning problem and let a states∈𝒮s\\in\\mathcal\{S\}represent a computational interface, such as a token prefix\. An actiona∈𝒜⁡\(s\)a\\in\\mathcal\{A\}\(s\)is a token, reasoning step, tool call, or reusable computation that produces the next states′=T⁡\(s,a\)s^\{\\prime\}=T\(s,a\)\. Letπ¯​\(a\|s\)\\bar\{\\pi\}\(a\|s\)denote a frozen language model used as a decoding or search prior\. For a trajectoryτ=\(s0,a0,s1,a1,…,sH\),\\tau=\(s\_\{0\},a\_\{0\},s\_\{1\},a\_\{1\},\\ldots,s\_\{H\}\),its probability under the frozen model isPπ¯​\(τ∣s0\)=∏t=0H−1π¯​\(at\|st\)\.P\_\{\\bar\{\\pi\}\}\(\\tau\\mid s\_\{0\}\)=\\prod\_\{t=0\}^\{H\-1\}\\bar\{\\pi\}\(a\_\{t\}\|s\_\{t\}\)\.Consequently,log⁡Pπ¯​\(τ∣s0\)=∑t=0H−1log⁡π¯​\(at∣st\)\.\\log P\_\{\\bar\{\\pi\}\}\(\\tau\\mid s\_\{0\}\)=\\sum\_\{t=0\}^\{H\-1\}\\log\\bar\{\\pi\}\(a\_\{t\}\\mid s\_\{t\}\)\.LetRx​\(y\)∈\{0,1\}R\_\{x\}\(y\)\\in\\\{0,1\\\}be a terminal verifier applied to a complete responseyy\. We write𝒴x\+​\(s\)=\{τ:τ​begins at​s​and terminates at​y​with​Rx​\(y\)=1\}\\mathcal\{Y\}^\{\+\}\_\{x\}\(s\)=\\left\\\{\\tau:\\tau\\text\{ begins at \}s\\text\{ and terminates at \}y\\text\{ with \}R\_\{x\}\(y\)=1\\right\\\}for the set of verified successful continuations fromss\. A verified trajectory may receive a terminal quality scoreRx​\(τ\)R\_\{x\}\(\\tau\)\.𝒮T\\mathcal\{S\}\_\{\\mathrm\{T\}\}is the set of terminal states, andRx​\(s\)R\_\{x\}\(s\)is the terminal score for taskxx\.

Compositional reasoning and generalization\.We call a solution*compositional*when it is a sequence of reusable computations,τ=f1∘⋯∘fd\\tau=f\_\{1\}\\circ\\cdots\\circ f\_\{d\}, in which each fragmentfif\_\{i\}, such as a reduction, a theorem application, or an arithmetic step, starts at the state produced by the previous one\.*Compositional reasoning*is the ability to produce such a sequence for a given problem\.*Compositional generalization*is the ability to solve problems whose solutions combine known fragments in a way that has not been observed before\([Lake and Baroni, 2018](https://arxiv.org/html/2610.02478#bib.bib44);[Keysers et al\., 2020](https://arxiv.org/html/2610.02478#bib.bib45);[Press et al\., 2023](https://arxiv.org/html/2610.02478#bib.bib46)\)\. In this paper, “not observed” has a specific meaning: every fragment of the solution may already have appeared in some rollout, but never all of them together in a single one\. The question we study is how a learner can turn fragments found in separate attempts into a verified solution that it was never able to sample\.

Expected\-Return RL\.In a deterministic computation graph, the corresponding Bellman equations areQπ¯​\(s,a\)=r⁡\(s,a\)\+Vπ¯​\(T⁡\(s,a\)\)Q^\{\\bar\{\\pi\}\}\(s,a\)=r\(s,a\)\+V^\{\\bar\{\\pi\}\}\(T\(s,a\)\),Vπ¯​\(s\)=∑a∈𝒜⁡\(s\)π¯​\(a∣s\)​Qπ¯​\(s,a\)\.V^\{\\bar\{\\pi\}\}\(s\)=\\sum\_\{a\\in\\mathcal\{A\}\(s\)\}\\bar\{\\pi\}\(a\\mid s\)Q^\{\\bar\{\\pi\}\}\(s,a\)\.With binary verification on a deterministic computation graph, the classical Bellman equation isVπ¯​\(s\)=∑aπ¯​\(a∣s\)​Vπ¯​\(T⁡\(s,a\)\)V^\{\\bar\{\\pi\}\}\(s\)=\\sum\_\{a\}\\bar\{\\pi\}\(a\\mid s\)\\,V^\{\\bar\{\\pi\}\}\\bigl\(T\(s,a\)\\bigr\)withVπ¯​\(y\)=Rx​\(y\)V^\{\\bar\{\\pi\}\}\(y\)=R\_\{x\}\(y\)at terminals\. It uses two operations: probabilities of successive steps are*multiplied*, and probabilities of alternative actions are*added*\. Unrolling the recursion yields

Vπ¯​\(s\)=∑τ∈𝒴x\+​\(s\)∏tπ¯​\(at∣st\)=∑τ∈𝒴x\+​\(s\)Pπ¯​\(τ∣s\)\.V^\{\\bar\{\\pi\}\}\(s\)=\\sum\_\{\\tau\\in\\mathcal\{Y\}^\{\+\}\_\{x\}\(s\)\}\\ \\prod\_\{t\}\\bar\{\\pi\}\(a\_\{t\}\\mid s\_\{t\}\)=\\sum\_\{\\tau\\in\\mathcal\{Y\}^\{\+\}\_\{x\}\(s\)\}P\_\{\\bar\{\\pi\}\}\(\\tau\\mid s\)\.\(1\)The classical value therefore has a direct operational meaning:*Vπ¯​\(s\)V^\{\\bar\{\\pi\}\}\(s\)is the probability that one continuation sampled fromπ¯\\bar\{\\pi\}, beginning atss, will eventually be accepted by the verifier\.*

![Refer to caption](https://arxiv.org/html/2610.02478v1/Images/fig_nonsuff_C_branches.png)Figure 2:A difference between expectedVVand maxMMcontinuation\.
## 3The Algebra of Expected Return

Expected return is a path sum in the semiring\(ℝ≥0,\+,×\)\(\\mathbb\{R\}\_\{\\geq 0\},\+,\\times\)\(Eq\.[1](https://arxiv.org/html/2610.02478#S2.E1)\): steps along a path combine by⊗=×\\otimes=\\times, and alternative paths combine by⊕=\+\\oplus=\+\. The two operations play different roles\. We keep the first and identify the second as the source of the problem\.

Multiplying step probabilities is the autoregressive factorization of the model\. In log space it becomes a sum of fragment scores: for an edgef=\(s,uf,s′\)f=\(s,u\_\{f\},s^\{\\prime\}\)and a pathτ\\tau,

w⁡\(f\)=∑j=1\|uf\|log⁡π¯​\(uf,j∣x,s,uf,<j\),W⁡\(τ\)=∑f∈τw⁡\(f\)=log⁡Pπ¯​\(τ∣s\)\.w\(f\)=\\sum\_\{j=1\}^\{\|u\_\{f\}\|\}\\log\\bar\{\\pi\}\(u\_\{f,j\}\\mid x,s,u\_\{f,<j\}\),\\qquad W\(\\tau\)=\\sum\_\{f\\in\\tau\}w\(f\)=\\log P\_\{\\bar\{\\pi\}\}\(\\tau\\mid s\)\.\(2\)A composed path is scored from its fragments without resampling, and because multiplication distributes over addition, the value admits dynamic programming\.

Adding the probabilities of alternative continuations has three properties\. Each is a strength when the goal is the success probability of a single sample, and a weakness when the goal is to retain and compose computations\.*\(i\) Addition is not selective\.*a\+ba\+bis the score of no single path, so the value reports*how much*of the actor succeeds,not*which*computation succeeds \(Observation[1](https://arxiv.org/html/2610.02478#Thmtheorem1)\)\.*\(ii\) Addition acts on normalized weights\.*Since∑aπ⁡\(a∣s\)=1\\sum\_\{a\}\\pi\(a\\mid s\)=1, raising one alternative lowers the others \(Proposition[1](https://arxiv.org/html/2610.02478#Thmproposition1)\)\.*\(iii\) Addition is not idempotent\.*a\+a=2​aa\+a=2a: a computation found twice counts twice, so what is sampled often is reinforced more \(Appendix[A\.3](https://arxiv.org/html/2610.02478#A1.SS3)\)\.

The sum does not say which computation succeeds\.Composition needs the most accessible verified continuation, the one to reuse:

Mπ¯​\(s\)=maxτ∈𝒴x\+​\(s\)⁡Pπ¯​\(τ∣s\)\.M^\{\\bar\{\\pi\}\}\(s\)=\\max\_\{\\tau\\in\\mathcal\{Y\}^\{\+\}\_\{x\}\(s\)\}P\_\{\\bar\{\\pi\}\}\(\\tau\\mid s\)\.\(3\)
###### Observation 1\(Non\-sufficiency\)\.

No functionggsatisfiesMπ¯​\(s\)=g⁡\(Vπ¯​\(s\)\)M^\{\\bar\{\\pi\}\}\(s\)=g\\bigl\(V^\{\\bar\{\\pi\}\}\(s\)\\bigr\)for all states and continuation sets\.

###### Proof\.

Let𝒴x\+​\(s\)=\{τ1\}\\mathcal\{Y\}^\{\+\}\_\{x\}\(s\)=\\\{\\tau\_\{1\}\\\}withPπ¯​\(τ1∣s\)=0\.5P\_\{\\bar\{\\pi\}\}\(\\tau\_\{1\}\\mid s\)=0\.5, and𝒴x\+​\(s′\)=\{τ2,τ3\}\\mathcal\{Y\}^\{\+\}\_\{x\}\(s^\{\\prime\}\)=\\\{\\tau\_\{2\},\\tau\_\{3\}\\\}withPπ¯​\(τ2∣s′\)=Pπ¯​\(τ3∣s′\)=0\.25P\_\{\\bar\{\\pi\}\}\(\\tau\_\{2\}\\mid s^\{\\prime\}\)=P\_\{\\bar\{\\pi\}\}\(\\tau\_\{3\}\\mid s^\{\\prime\}\)=0\.25\. ThenVπ¯​\(s\)=Vπ¯​\(s′\)=0\.5V^\{\\bar\{\\pi\}\}\(s\)=V^\{\\bar\{\\pi\}\}\(s^\{\\prime\}\)=0\.5, whileMπ¯​\(s\)=0\.5M^\{\\bar\{\\pi\}\}\(s\)=0\.5andMπ¯​\(s′\)=0\.25M^\{\\bar\{\\pi\}\}\(s^\{\\prime\}\)=0\.25\. ∎

The gap can be arbitrarily large:nncontinuations of probability1/n1/ngiveVπ¯=1V^\{\\bar\{\\pi\}\}=1butMπ¯=1/nM^\{\\bar\{\\pi\}\}=1/n\. The converse also fails, since\{0\.5\}\\\{0\.5\\\}and\{0\.5,0\.25\}\\\{0\.5,\\,0\.25\\\}shareMπ¯=0\.5M^\{\\bar\{\\pi\}\}=0\.5but differ inVπ¯V^\{\\bar\{\\pi\}\}\. Once alternatives are added, the sum cannot tell which computations produced it \(Fig\.[2](https://arxiv.org/html/2610.02478#S2.F2)\)\.

The sum can forget a verified solution\.We call a value*policy\-indexed*if it depends only on the current policy,Vt​\(s\)=Φ⁡\(πθt,s\)V\_\{t\}\(s\)=\\Phi\(\\pi\_\{\\theta\_\{t\}\},s\)\. Every on\-policy expected\-return method is policy\-indexed, with or without baselines, critics, or entropy bonuses\.

###### Proposition 1\(Policy\-indexed values forget\)\.

Letsshave two actionsa,ba,bwith independent softmax logits\. The continuation afterbbalways succeeds,Vπ¯​\(T⁡\(s,b\)\)=1V^\{\\bar\{\\pi\}\}\(T\(s,b\)\)=1, and the continuation afteraasucceeds half the time,Vπ¯​\(T⁡\(s,a\)\)=12V^\{\\bar\{\\pi\}\}\(T\(s,a\)\)=\\tfrac\{1\}\{2\}\. Suppose a batch samples onlyaaatss, some of these rollouts succeed, and the group baseline is below11, soaareceives estimated advantageA^\>0\\widehat\{A\}\>0\. Then after one policy\-gradient step,π\+​\(b∣s\)<π⁡\(b∣s\)\\pi^\{\+\}\(b\\mid s\)<\\pi\(b\\mid s\)andV\+π¯​\(s\)<Vπ¯​\(s\)V^\{\\bar\{\\pi\}\}\_\{\+\}\(s\)<V^\{\\bar\{\\pi\}\}\(s\), even though no rollout observedbband the verifier’s judgement of the continuation throughbbis unchanged\.

###### Proof\.

From∂logπ\(a∣s\)/∂zj=𝟏\{j=a\}−π\(j∣s\)\\partial\\log\\pi\(a\\mid s\)/\\partial z\_\{j\}=\\mathbf\{1\}\\\{j=a\\\}\-\\pi\(j\\mid s\), the step givesΔ​za=η​A^​\(1−π⁡\(a∣s\)\)\>0\\Delta z\_\{a\}=\\eta\\widehat\{A\}\\,\(1\-\\pi\(a\\mid s\)\)\>0andΔ​zb=−η​A^​π​\(b∣s\)<0\\Delta z\_\{b\}=\-\\eta\\widehat\{A\}\\,\\pi\(b\\mid s\)<0, soπ\+​\(b∣s\)<π⁡\(b∣s\)\\pi^\{\+\}\(b\\mid s\)<\\pi\(b\\mid s\)\. Only the logits atsschange, soVπ¯​\(s\)=12​π​\(a∣s\)\+π⁡\(b∣s\)=12\+12​π​\(b∣s\)V^\{\\bar\{\\pi\}\}\(s\)=\\tfrac\{1\}\{2\}\\pi\(a\\mid s\)\+\\pi\(b\\mid s\)=\\tfrac\{1\}\{2\}\+\\tfrac\{1\}\{2\}\\pi\(b\\mid s\)strictly decreases\. ∎

A policy\-indexed learner can restoreπ⁡\(b∣s\)\\pi\(b\\mid s\)only by samplingbbagain\. Normalization makes reinforcement zero\-sum, so a verified capability can disappear without ever being refuted\.

### 3\.1Replacing the aggregation

![Refer to caption](https://arxiv.org/html/2610.02478v1/Images/fig_forgetting_vs_retention.png)Figure 3:*Lemma[3](https://arxiv.org/html/2610.02478#Thmtheorem3)schematic illustration*The diagnosis points to a single change\. We keep composition by adding log\-scores along a path \(Eq\.[2](https://arxiv.org/html/2610.02478#S3.E2)\), keep the model’s log\-probability as the score of each path, and replace only the operation that combines alternatives\. Write⊕\\oplusfor that operation\. The value of a statessis the aggregate of the scores of its verified continuationsV⊕​\(s\)=⨁τ∈𝒴x\+​\(s\)W⁡\(τ\)V\_\{\\oplus\}\(s\)=\\bigoplus\_\{\\tau\\in\\mathcal\{Y\}^\{\+\}\_\{x\}\(s\)\}W\(\\tau\), where⊕\\oplusis commutative and associative, so that the value does not depend on the order in which continuations were found\. Expected return is one choice: with⊕=LSE\\oplus=\\LSE, Eq\.[1](https://arxiv.org/html/2610.02478#S2.E1)givesV⊕​\(s\)=log⁡Vπ¯​\(s\)V\_\{\\oplus\}\(s\)=\\log V^\{\\bar\{\\pi\}\}\(s\)\. For composition, we ask two things of the value\.

Certification\.The value ofssis always the score of one of its verified continuations:a⊕b∈\{a,b\}a\\oplus b\\in\\\{a,b\\\}\. The value then names a concrete path that can be replayed, verified, and joined with others\.

Retention\.Finding a new verified continuation never lowers the value:V⊕​\(s\)V\_\{\\oplus\}\(s\)cannot decrease when a path is added to𝒴x\+​\(s\)\\mathcal\{Y\}^\{\+\}\_\{x\}\(s\)\.

###### Theorem 2\(Certification and retention force the maximum\)\.

If⊕\\oplussatisfies\(Certification\)and\(Retention\), thena⊕b=max⁡\{a,b\}a\\oplus b=\\max\\\{a,b\\\}\. With additive scores, the resulting structure is\(ℝ∪\{−∞\},max,\+\)\(\\mathbb\{R\}\\cup\\\{\-\\infty\\\},\\max,\+\), the max–plus or tropical semiring\.

###### Proof\.

Adding a continuation of scorebbto one of scoreaagivesa⊕b≥aa\\oplus b\\geq aby \(Retention\); addingaatobbgivesb⊕a≥bb\\oplus a\\geq b, andb⊕a=a⊕bb\\oplus a=a\\oplus b\. Hencea⊕b≥max⁡\{a,b\}a\\oplus b\\geq\\max\\\{a,b\\\}\. By \(Certification\),a⊕ba\\oplus bequalsaaorbb, so it equalsmax⁡\{a,b\}\\max\\\{a,b\\\}\. ∎

Each requirement rules out a familiar choice\. Addition andLSE\\LSEsatisfy \(Retention\) but fail \(Certification\): their value exceeds every term and is the score of no path\. The minimum satisfies \(Certification\) but fails \(Retention\)\. Every policy\-indexed value fails \(Retention\) over the course of training, by Proposition[1](https://arxiv.org/html/2610.02478#Thmproposition1): its value can fall although no verified continuation was removed\.

By Theorem[2](https://arxiv.org/html/2610.02478#Thmtheorem2), the value of a state is the score of its best verified continuation,

Vtropπ¯​\(s\)=maxτ∈𝒴x\+​\(s\)⁡W⁡\(τ\)=log⁡Mπ¯​\(s\),V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s\)=\\max\_\{\\tau\\in\\mathcal\{Y\}^\{\+\}\_\{x\}\(s\)\}W\(\\tau\)=\\log M^\{\\bar\{\\pi\}\}\(s\),\(4\)which is exactly the quantity that Observation[1](https://arxiv.org/html/2610.02478#Thmtheorem1)shows expected return cannot supply\. It also has a direct meaning: it is the distance from the actor to its nearest verified computation,Vtropπ¯\(s\)=−minτ∈𝒴x\+​\(s\)DKL\(δτ∥Pπ¯\(⋅∣s\)\)V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s\)=\-\\min\_\{\\tau\\in\\mathcal\{Y\}^\{\+\}\_\{x\}\(s\)\}D\_\{\\mathrm\{KL\}\}\\bigl\(\\delta\_\{\\tau\}\\,\\\|\\,P\_\{\\bar\{\\pi\}\}\(\\cdot\\mid s\)\\bigr\), whereδτ\\delta\_\{\\tau\}executesτ\\taudeterministically \(Lemma[5](https://arxiv.org/html/2610.02478#Thmtheorem5), Appendix[A\.2](https://arxiv.org/html/2610.02478#A1.SS2)\)\. Section[4](https://arxiv.org/html/2610.02478#S4)builds reinforcement learning on this value\.

The maximum reverses the three failures\.It is*selective*: the value is the score of one path, recoverable by backpointers \(Observation[1](https://arxiv.org/html/2610.02478#Thmtheorem1)\)\. It is*idempotent*:max⁡\{a,a\}=a\\max\\\{a,a\\\}=a, so rediscovering a computation changes nothing \(Appendix[A\.3](https://arxiv.org/html/2610.02478#A1.SS3)\)\. And it is*monotone under set growth*, which the normalized sum cannot be \(Proposition[1](https://arxiv.org/html/2610.02478#Thmproposition1)\)\. Let𝒢t=\(𝒮t,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{S\}\_\{t\},\\mathcal\{E\}\_\{t\}\)be the graph of transitions discovered by iterationtt,𝒞t\+​\(s\)\\mathcal\{C\}^\{\+\}\_\{t\}\(s\)the verified continuations constructible from it, and

Vcap​\[t\]​\(s\)=maxτ∈𝒞t\+​\(s\)⁡Rx​\(τ\),max⁡∅=−∞\.V\_\{\\mathrm\{cap\}\}\[t\]\(s\)=\\max\_\{\\tau\\in\\mathcal\{C\}^\{\+\}\_\{t\}\(s\)\}R\_\{x\}\(\\tau\),\\qquad\\max\\emptyset=\-\\infty\.\(5\)
###### Lemma 3\(Retained capability is monotone\)\.

If the verifier is fixed and the memory retains its discoveries,ℰt⊆ℰt\+1\\mathcal\{E\}\_\{t\}\\subseteq\\mathcal\{E\}\_\{t\+1\}, thenVcap​\[t\+1\]​\(s\)≥Vcap​\[t\]​\(s\)V\_\{\\mathrm\{cap\}\}\[t\+1\]\(s\)\\geq V\_\{\\mathrm\{cap\}\}\[t\]\(s\)for every statessand iterationtt\.

###### Proof\.

ℰt⊆ℰt\+1\\mathcal\{E\}\_\{t\}\\subseteq\\mathcal\{E\}\_\{t\+1\}implies𝒞t\+​\(s\)⊆𝒞t\+1\+​\(s\)\\mathcal\{C\}^\{\+\}\_\{t\}\(s\)\\subseteq\\mathcal\{C\}^\{\+\}\_\{t\+1\}\(s\), and the maximum is monotone under inclusion\. ∎

Under the maximum, discovery enlarges a set, and a maximum over a growing set cannot fall\. Distributivity also survives the change,c\+max⁡\{a,b\}=max⁡\{c\+a,c\+b\}c\+\\max\\\{a,b\\\}=\\max\\\{c\+a,\\,c\+b\\\}, so a best prefix and a best suffix can be chosen independently at a shared state \(Eq\.[9](https://arxiv.org/html/2610.02478#S4.E9)\), and dynamic programming over exponentially many compositions remains possible\.

## 4Tropical Reinforcement Learning

Section[3\.1](https://arxiv.org/html/2610.02478#S3.SS1)fixed the value: the score of the best verified continuation\. This section turns it into reinforcement learning\. We write its Bellman equations \(Section[4\.1](https://arxiv.org/html/2610.02478#S4.SS1)\), prove the property that separates it from classical RL, namely that improvement composes \(Section[4\.2](https://arxiv.org/html/2610.02478#S4.SS2)\), and build the algorithmTropicon it \(Section[4\.3](https://arxiv.org/html/2610.02478#S4.SS3)\)\.

### 4\.1Tropical Bellman equations

Withλ≥0\\lambda\\geq 0weighing how much the model’s likelihood counts, the tropical Bellman equations are

Qtropπ¯​\(s,a\)=λ​log⁡π¯​\(a∣s\)\+r⁡\(s,a\)\+Vtropπ¯​\(T⁡\(s,a\)\),Vtropπ¯​\(s\)=maxa∈𝒜⁡\(s\)⁡Qtropπ¯​\(s,a\)\.Q^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s,a\)=\\lambda\\log\\bar\{\\pi\}\(a\\mid s\)\+r\(s,a\)\+V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\\bigl\(T\(s,a\)\\bigr\),\\qquad V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s\)=\\max\_\{a\\in\\mathcal\{A\}\(s\)\}Q^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s,a\)\.\(6\)The classical recursion averages over actions; this one takes the best\. In max–plus notation it is linear,Vtropπ¯​\(s\)=⨁a\(λ​log⁡π¯​\(a∣s\)⊗r⁡\(s,a\)⊗Vtropπ¯​\(T⁡\(s,a\)\)\)V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s\)=\\bigoplus\_\{a\}\\bigl\(\\lambda\\log\\bar\{\\pi\}\(a\\mid s\)\\otimes r\(s,a\)\\otimes V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(T\(s,a\)\)\\bigr\), and unrolled it is the score of the best path,

Vtropπ¯​\(s\)=maxτ⁡\{λ​log⁡Pπ¯​\(τ∣s\)\+∑tr⁡\(st,at\)\+Rx​\(sH\)\}\.V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s\)=\\max\_\{\\tau\}\\Bigl\\\{\\lambda\\log P\_\{\\bar\{\\pi\}\}\(\\tau\\mid s\)\+\\sum\_\{t\}r\(s\_\{t\},a\_\{t\}\)\+R\_\{x\}\(s\_\{H\}\)\\Bigr\\\}\.\(7\)With a binary verifier, internal rewards are zero, accepted terminals have value00and rejected ones−∞\-\\infty, so failed paths drop out\. Atλ=1\\lambda=1,

Vtropπ¯​\(s\)=maxτ∈𝒴x\+​\(s\)⁡log⁡Pπ¯​\(τ∣s\),V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s\)=\\max\_\{\\tau\\in\\mathcal\{Y\}^\{\+\}\_\{x\}\(s\)\}\\log P\_\{\\bar\{\\pi\}\}\(\\tau\\mid s\),\(8\)which is the tropical value of Eq\.[4](https://arxiv.org/html/2610.02478#S3.E4)\. Two special cases place the equation among known objects\. Atλ=0\\lambda=0the model drops out, and Eq\.[6](https://arxiv.org/html/2610.02478#S4.E6)is classical Bellman optimality on a deterministic graph; its value is the capability of Lemma[3](https://arxiv.org/html/2610.02478#Thmtheorem3), which training can never lower\. Atλ=1\\lambda=1it is Viterbi decoding underπ¯\\bar\{\\pi\}restricted to verified paths, and it is the zero\-temperature limit of the soft Bellman equation\([Ziebart, 2010](https://arxiv.org/html/2610.02478#bib.bib18);[Haarnoja et al\., 2018](https://arxiv.org/html/2610.02478#bib.bib19)\)\. What is new is not the recursion but what it is used for: a value that composes, and a learning rule built on it\.

Scores add along paths and addition distributes over max, so the best solution through a statesssplits into a best prefix and a best suffix,

maxp∈𝒫t​\(s\),q∈𝒞t\+​\(s\)⁡W⁡\(p∘q\)=maxp∈𝒫t​\(s\)⁡W⁡\(p\)\+maxq∈𝒞t\+​\(s\)⁡W⁡\(q\),\\max\_\{p\\in\\mathcal\{P\}\_\{t\}\(s\),\\,q\\in\\mathcal\{C\}^\{\+\}\_\{t\}\(s\)\}W\(p\\circ q\)=\\max\_\{p\\in\\mathcal\{P\}\_\{t\}\(s\)\}W\(p\)\+\\max\_\{q\\in\\mathcal\{C\}^\{\+\}\_\{t\}\(s\)\}W\(q\),\(9\)where𝒫t​\(s\)\\mathcal\{P\}\_\{t\}\(s\)are retained prefixes ending atssand𝒞t\+​\(s\)\\mathcal\{C\}^\{\+\}\_\{t\}\(s\)retained verified suffixes starting there\. The two halves may come from different rollouts\. Eq\.[9](https://arxiv.org/html/2610.02478#S4.E9)requires that the score of a suffix depend only on the state where it starts, not on how that state was reached\. Our approach therefore prompts the actor with the problem and the current environment state only,π¯​\(u∣x,s\)\\bar\{\\pi\}\(u\\mid x,s\), and includes the step count inssso that the graph is acyclic; any joined path is also replayed and rescored before it is used\. A solution ofddfragments, each produced with probability aboutρ\\rho, takes aboutρ−d\\rho^\{\-d\}rollouts to sample in one piece, but is available to Eq\.[9](https://arxiv.org/html/2610.02478#S4.E9)as soon as each fragment has been found once\. Table[1](https://arxiv.org/html/2610.02478#S4.T1)lists how the change from sum to max alters every object built on the Bellman equation\.

Table 1:Classical and tropical RL on the same verified paths\. Proofs in Appendix[A](https://arxiv.org/html/2610.02478#A1)\.
### 4\.2Improvement composes

The central difference between the two algebras shows up when the actor is trained\. Under expected return, reinforcing one solution takes probability from the others, and a verified solution can lose value without ever being refuted \(Proposition[1](https://arxiv.org/html/2610.02478#Thmproposition1)\)\. Under the maximum, the opposite holds\.

###### Theorem 4\(Compositional policy improvement\)\.

Let𝒢\\mathcal\{G\}be the retained graph of a problemxx, and for each statesslet𝒞⁡\(s\)\\mathcal\{C\}\(s\)be the verified paths in𝒢\\mathcal\{G\}that start atss\. Let the actor be a softmax policy with separate logits at each state, and letVθ​\(s\)=maxτ∈𝒞⁡\(s\)⁡log⁡Pθ​\(τ∣s\)V\_\{\\theta\}\(s\)=\\max\_\{\\tau\\in\\mathcal\{C\}\(s\)\}\\log P\_\{\\theta\}\(\\tau\\mid s\)\. Letτ⋆\\tau^\{\\star\}be the best verified path from the root, and take one gradient step on its log\-likelihood,θ′=θ\+η​∇θ​log⁡Pθ​\(τ⋆∣x\)\\theta^\{\\prime\}=\\theta\+\\eta\\,\\nabla\_\{\\theta\}\\log P\_\{\\theta\}\(\\tau^\{\\star\}\\mid x\), with anyη\>0\\eta\>0\. Then:

1. \(i\)Vθ′​\(s\)≥Vθ​\(s\)V\_\{\\theta^\{\\prime\}\}\(s\)\\geq V\_\{\\theta\}\(s\)for every statessin𝒢\\mathcal\{G\};
2. \(ii\)if the best verified path fromsspasses through a stateuuofτ⋆\\tau^\{\\star\}, thenVθ′​\(s\)−Vθ​\(s\)≥Vθ′​\(u\)−Vθ​\(u\)\>0V\_\{\\theta^\{\\prime\}\}\(s\)\-V\_\{\\theta\}\(s\)\\geq V\_\{\\theta^\{\\prime\}\}\(u\)\-V\_\{\\theta\}\(u\)\>0\.

Best paths are taken with ties broken by a fixed rule\. Proof in Appendix[A\.4](https://arxiv.org/html/2610.02478#A1.SS4)\.

The statessin \(ii\) need not lie onτ⋆\\tau^\{\\star\}and may never have been trained from\. Its best solution can be a prefix from one rollout joined atuuto a suffix trained as part of another, and it inherits the full gain made on that suffix\. The reason is a property of the maximum: the step can lower the probability of actions that are not on the best path, but no best path uses them, so no value sees the loss\. Under a sum every alternative counts, and the loss is always seen\.

The theorem is exact for an actor with separate parameters per state\. With shared parameters, as in a language model, a step onτ⋆\\tau^\{\\star\}also moves the actor at other states, and the guarantee holds up to this interference\.

Tropical improves pass@kk\.Letp⁡\(x\)=∑τ∈𝒴x\+Pθ​\(τ∣x\)p\(x\)=\\sum\_\{\\tau\\in\\mathcal\{Y\}^\{\+\}\_\{x\}\}P\_\{\\theta\}\(\\tau\\mid x\)be the pass@1 of problemxx, so pass@kkis1−\(1−p⁡\(x\)\)k1\-\(1\-p\(x\)\)^\{k\}\. The best verified path is one of the paths in this sum, so for every problem

log⁡p⁡\(x\)≥Vtropπ¯​\(s0​\(x\)\),pass@​k​\(x\)≥1−\(1−eVtropπ¯​\(s0​\(x\)\)\)k\.\\log p\(x\)\\;\\geq\\;V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s\_\{0\}\(x\)\),\\qquad\\text\{pass@\}k\(x\)\\;\\geq\\;1\-\\bigl\(1\-e^\{V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s\_\{0\}\(x\)\)\}\\bigr\)^\{k\}\.\(10\)Raising the tropical value raises a lower bound on both quantities for every problem\. The bound does not by itself force pass@1 up; what it explains is*which*problems improve\. The expected\-return gradient on problemxxis∇p\(x\)=p\(x\)∇logp\(x\)\\nabla p\(x\)=p\(x\)\\,\\nabla\\log p\(x\), so a problem solved once in a hundred attempts receives a hundredth of the push\. The tropical gradient gives every problem with a verified path unit weight on that path \(Corollary[3](https://arxiv.org/html/2610.02478#Thmcorollary3)\), however rare, and the archive supplies such paths, including composed ones, for problems the actor almost never solves alone\. Pass@kkis decided by exactly these problems: whenp⁡\(x\)p\(x\)is small, pass@k≈k​p​\(x\)k\\approx k\\,p\(x\)\. Expected return spends its gradient on problems that are already solved, which is why its pass@kkcurve flattens toward its pass@1 \(Figure[1](https://arxiv.org/html/2610.02478#S1.F1)\)\. Empirically,Tropicalso has the highest pass@1 on every task and model we test \(Table[2](https://arxiv.org/html/2610.02478#S5.T2)\)\.

TakeawayClassical RL:improving one solution can erase another\. Tropical RL:improving one solution never lowers any other, and every solution that shares a piece of it gains at least as much as that piece\.

### 4\.3Tropic: tropical policy optimization

Objective\.Tropicmakes the best verified solution of each problem as likely as possible:

Jtrop​\(θ\)=𝔼x∼μ​\[maxτ∈𝒴x\+​\(s0​\(x\)\)⁡log⁡Pθ​\(τ∣x\)\]\.J\_\{\\mathrm\{trop\}\}\(\\theta\)=\\mathbb\{E\}\_\{x\\sim\\mu\}\\Bigl\[\\max\_\{\\tau\\in\\mathcal\{Y\}^\{\+\}\_\{x\}\(s\_\{0\}\(x\)\)\}\\log P\_\{\\theta\}\(\\tau\\mid x\)\\Bigr\]\.\(11\)
Memory\.For each problem,Tropickeeps a graph whose edges are all valid stepsf=\(s,uf,s′\)f=\(s,u\_\{f\},s^\{\\prime\}\)seen so far\. This includes steps from failed attempts, since a later attempt may succeed from where they ended\. Complete paths that are replayed from the start and accepted by the verifier form the*archive*\. At the start of each iteration the actor is frozen asπ¯t\\bar\{\\pi\}\_\{t\}, and every stored step is rescored under it,wt​\(f\)=log⁡π¯t​\(uf∣x,s\)w\_\{t\}\(f\)=\\log\\bar\{\\pi\}\_\{t\}\(u\_\{f\}\\mid x,s\)\.

Prefix and suffix values\.For every state,Tropiccomputes how easily the actor can*finish*from it \(VtV\_\{t\}\) and how easily it can*reach*it \(FtF\_\{t\}\):

Vt​\(s\)=maxf=\(s,uf,s′\)⁡\{wt​\(f\)\+Vt​\(s′\)\},Ft​\(s′\)=maxf=\(s,uf,s′\)⁡\{Ft​\(s\)\+wt​\(f\)\}\.V\_\{t\}\(s\)=\\max\_\{f=\(s,u\_\{f\},s^\{\\prime\}\)\}\\bigl\\\{w\_\{t\}\(f\)\+V\_\{t\}\(s^\{\\prime\}\)\\bigr\\\},\\qquad F\_\{t\}\(s^\{\\prime\}\)=\\max\_\{f=\(s,u\_\{f\},s^\{\\prime\}\)\}\\bigl\\\{F\_\{t\}\(s\)\+w\_\{t\}\(f\)\\bigr\\\}\.\(12\)VtV\_\{t\}is the tropical Bellman equation \(Eq\.[6](https://arxiv.org/html/2610.02478#S4.E6)\) run backward from verified endings, andFtF\_\{t\}is the same recursion run forward from the start\. Their sumFt​\(s\)\+Vt​\(s\)F\_\{t\}\(s\)\+V\_\{t\}\(s\)is the score of the best verified solution throughss\(Eq\.[9](https://arxiv.org/html/2610.02478#S4.E9)\)\. Both passes take time linear in the size of the graph\.

Growing the memory\.New paths enter the graph in two ways\.*Sampling\.*Each problem receivesGGgroups ofnnattempts\. The first group starts from the initial state, and the others start from*frontier*states, which the graph can reach but not yet finish from \(Vt​\(s\)=−∞V\_\{t\}\(s\)=\-\\infty\)\. To choose a start,Tropicfirst picks the depthr⋆r^\{\\star\}from which the fewest attempts have started so far\. At that depth it picks the state that is easy to reach and rarely tried:

s⋆=arg⁡maxs​at depth​r⋆​\{Ft​\(s\)−κ​log⁡\(1\+ns\)\},s^\{\\star\}=\\arg\\max\_\{s\\ \\text\{at depth\}\\ r^\{\\star\}\}\\bigl\\\{F\_\{t\}\(s\)\-\\kappa\\log\(1\+n\_\{s\}\)\\bigr\\\},\(13\)wherensn\_\{s\}is the number of earlier attempts started fromss\. Each new attempt is prepended with the best known prefix tos⋆s^\{\\star\}, then replayed and verified as a complete path\.*Composition\.*Wherever a state has both a known way in and a known way out,Tropicjoins theLLbest prefixes with theLLbest suffixes, then replays and verifies each joined path\. Accepted joins enter the archive\. This is howTropicfinds solutions the actor never produced in one piece\.

Training\.For each problem,Tropicselects up toKKarchived pathsℬx,t\\mathcal\{B\}\_\{x,t\}\. The first is the best pathτ1=τx⋆\\tau\_\{1\}=\\tau^\{\\star\}\_\{x\}\. The rest are the paths with the highest coverage scorect\(τ\)=∑f∈τ\(1\+mt\(f\)\)−1/2c\_\{t\}\(\\tau\)=\\sum\_\{f\\in\\tau\}\(1\+m\_\{t\}\(f\)\)^\{\-1/2\}, wheremt​\(f\)m\_\{t\}\(f\)is the number of earlier iterations in which stepffwas trained\. These extra paths rehearse rarely trained steps so they are not forgotten \(Proposition[1](https://arxiv.org/html/2610.02478#Thmproposition1)\)\. The model then takes one gradient step on the per\-token log\-likelihood of the selected paths, averaged over the set𝒳t\+\\mathcal\{X\}^\{\+\}\_\{t\}of problems that have at least one:

ℒt\(θ\)=−1\|𝒳t\+\|∑x∈𝒳t\+1\|ℬx,t\|∑τ∈ℬx,t1TτlogPθ\(τ∣x\),\\mathcal\{L\}\_\{t\}\(\\theta\)=\-\\frac\{1\}\{\|\\mathcal\{X\}^\{\+\}\_\{t\}\|\}\\sum\_\{x\\in\\mathcal\{X\}^\{\+\}\_\{t\}\}\\frac\{1\}\{\|\\mathcal\{B\}\_\{x,t\}\|\}\\sum\_\{\\tau\\in\\mathcal\{B\}\_\{x,t\}\}\\frac\{1\}\{T\_\{\\tau\}\}\\log P\_\{\\theta\}\(\\tau\\mid x\),\(14\)whereTτT\_\{\\tau\}is the number of tokens inτ\\tau\. It has no reward weights, no baseline, and no term that pushes any path down\.

![Refer to caption](https://arxiv.org/html/2610.02478v1/Images/qwen_success_bars_left.png)Figure 4:Tropicperformance against the baselines under the same compute budget\.

## 5Related Work

Recent work shows that RL post\-training can teach language models to compose skills they already have\([Yuan et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib39);[Abdulsalam et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib41);[Fu and Liu, 2026](https://arxiv.org/html/2610.02478#bib.bib42);[Kong et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib43)\)and can improve reasoning beyond the base model\([Wen et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib40)\), although its gains may stay within the base model’s sampling support\([Yue et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib38)\)\. Many methods improve RL training for LLMs: DAPO\([Yu et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib4)\)and SNR\-aware filtering\([Wang et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib11)\)address training collapse, GiGPO\([Feng et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib12)\)and VinePPO\([Kazemnejad et al\., 2024](https://arxiv.org/html/2610.02478#bib.bib27)\)refine step\-level credit, process supervision rewards intermediate steps\([Uesato et al\., 2022](https://arxiv.org/html/2610.02478#bib.bib35);[Lightman et al\., 2024](https://arxiv.org/html/2610.02478#bib.bib31)\), and resets have been used for credit assignment\([Samanta et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib28)\)\. All of these works optimize expected return, so a composition must be sampled in one piece before it is reinforced\. They are complementary to ours, which changes how alternative trajectories are aggregated\.

Other works move beyond expected return\. Several optimize pass@kkdirectly\([Brown et al\., 2024](https://arxiv.org/html/2610.02478#bib.bib32);[Tang et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib25);[Walder and Karkhanis, 2026](https://arxiv.org/html/2610.02478#bib.bib26)\), and MaxRL\([Tajwar et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib15)\)maximizes the logarithm of expected return, giving more weight to rarely solved problems\. Expected return sums the probabilities of verified paths, MaxRL takes the logarithm of this sum, and Tropical RL takes its maximum, the zero\-temperature limit in which alternatives are selected rather than summed\.

Closer to our method, tree search retains and extends promising partial trajectories\([Yao et al\., 2023b](https://arxiv.org/html/2610.02478#bib.bib33);[Zhang et al\., 2024](https://arxiv.org/html/2610.02478#bib.bib34)\), T\-STAR\([Li et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib24)\)grafts corrected steps onto shared trajectory structure, and[Liu et al\. \(2026\)](https://arxiv.org/html/2610.02478#bib.bib30)preserve correct prefixes when penalizing errors\. These methods reuse trajectories that were sampled;Tropicalso composes verified solutions that were never sampled in one piece\. We compare against T\-STAR in Section[6\.1](https://arxiv.org/html/2610.02478#S6.SS1)\. Finally, max\-plus methods have been used to compute or approximate value functions of known deterministic control problems\([Akian et al\., 2008](https://arxiv.org/html/2610.02478#bib.bib13);[McEneaney, 2006](https://arxiv.org/html/2610.02478#bib.bib29);[Berthier and Bach, 2020](https://arxiv.org/html/2610.02478#bib.bib14);[Gonçalves, 2021](https://arxiv.org/html/2610.02478#bib.bib17);[Bach, 2019](https://arxiv.org/html/2610.02478#bib.bib16)\)\. We instead use the max\-plus semiring to define the learning objective of a language\-model policy\.

Table 2:Results \(Qwen2\.5\-3B\-Instruct & Gemma 4 E4B\-it\)\.We report Success Rate \(↑\\uparrow, mean±\\pmstandard deviation over three independent training seeds\) and Generated Tokens per Episode \(↓\\downarrow\) on the held\-out evaluation set, together with end\-to\-end Training Wall\-Clock Time in hours \(↓\\downarrow\)\.
## 6Experiments and Results

Environments\.We evaluateTropicon four interactive tasks from RAGEN\-2\([Wang et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib11)\): \(i\)*Sokoban*\([Weber et al\., 2018](https://arxiv.org/html/2610.02478#bib.bib10)\), a grid\-based planning task in which the agent pushes boxes onto targets while avoiding irreversible dead ends so that solutions depend on reusing good partial prefixes, \(ii\)*Countdown*\([Katz et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib7)\), an exact\-target arithmetic task with many valid solutions in which intermediate results from different attempts can be recombined, \(iii\)*FrozenLake*\([Brockman et al\., 2016](https://arxiv.org/html/2610.02478#bib.bib9)\), a grid world with terminal holes and sparse rewards in which safe partial paths must be retained and extended, and \(iv\)*WebShop*\([Yao et al\., 2023a](https://arxiv.org/html/2610.02478#bib.bib8)\), a long\-horizon web\-shopping task in which search, navigation, and attribute selection must be composed under delayed feedback\. All environments are deterministic and resettable\. Further details are provided in App\.[B](https://arxiv.org/html/2610.02478#A2)\. Training and Baselines\.For each task, we train Qwen\-2\.5\-3B\-Instruct\([Qwen et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib6)\)and Gemma 4 E4B\-it\([Gemma Team, 2026](https://arxiv.org/html/2610.02478#bib.bib1)\)using PPO\([Schulman et al\., 2017](https://arxiv.org/html/2610.02478#bib.bib5)\), GRPO\([Shao et al\., 2024](https://arxiv.org/html/2610.02478#bib.bib36)\), DAPO\([Yu et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib4)\), RAGEN’s SNR\-Aware method\([Wang et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib11)\), andTropic\. All methods are trained under a matched experimental setup, using the same GPU, task\-relevant observations, rollout budget, environment workers, and the same observation representation\. We discuss the differences in restarts, replay, and stopping in App\.[C](https://arxiv.org/html/2610.02478#A3)\. We evaluate all methods across three independent training seeds on a predefined held\-out split of unseen instances\. We report the task success rate, end\-to\-end training time, and the average number of generated tokens per episode\. Results\.Table[2](https://arxiv.org/html/2610.02478#S5.T2)and Fig\.[4](https://arxiv.org/html/2610.02478#S4.F4)show thatTropicachieves the highest success rate on every task and for both models, while generating a comparable or smaller number of tokens and training faster in all but one setting\. The largest gains appear on Sokoban, where irreversible dead ends make complete solutions rare\.Tropicimproves over the strongest baseline \(SNR\-Aware\) by16\.216\.2points with Qwen and by6\.66\.6points with Gemma, and trains in1\.61\.6instead of2\.12\.1hours with Qwen\. On Countdown, where exact verification leaves most attempts without signal,Tropicgains5\.95\.9points over SNR\-Aware with Qwen and6\.06\.0points over GRPO with Gemma\. On FrozenLake, where a single misstep ends an episode, retaining safe partial paths yields9\.19\.1points over SNR\-Aware with Qwen and7\.27\.2points over DAPO with Gemma\. On WebShop, where late mistakes hide correct search and selection steps,Tropicimproves over SNR\-Aware by6\.96\.9points with Qwen and4\.64\.6points with Gemma, while training fastest with both models\. Among the non\-tropical baselines, no method is consistently strongest\. SNR\-Aware is the best baseline on every task with Qwen but the weakest on Countdown and FrozenLake with Gemma, and the ordering of PPO, GRPO, and DAPO changes from task to task, suggesting that refinements within the expected\-return objective do not transfer reliably across tasks and models\.Tropic, in contrast, is best in every setting and for both model families\.

### 6\.1Ablation Results

Table 3:Ablations and Cross\-Comparison \(Sokoban, Qwen2\.5\-3B\-Instruct\)\.Success rate, tokens per episode, training time, and*First\-Solve*\.MethodSuccess Rate \(↑\\uparrow\)Tokens \(↓\\downarrow\)Time \(h\) \(↓\\downarrow\)First\-Solve \(↑\\uparrow\)Base Model12\.89254\-\-\-\-MaxRL51\.30±\\pm2\.312022\.53\-\-GiGPO47\.60±\\pm2\.181993\.11\-\-GiGPO \+ T\-STAR53\.10±\\pm2\.181943\.80\-\-TROPIC \(No Comp\.\)40\.80±\\pm2\.262051\.450\.0TROPIC \(Root\-Only\)51\.80±\\pm2\.121961\.9224\.7±\\pm3\.2TROPIC \(Succ\.\-Only\)53\.30±\\pm1\.971921\.510\.0Full TROPIC58\.40±\\pm1\.831871\.5831\.6±\\pm3\.5

To isolate the contribution of each core component inTropic, we evaluate three ablations: \(i\)*No Composition*retains persistent memory and frontier acquisition but disables cross\-rollout graph recombination, restricting updates strictly to directly sampled paths, \(ii\)*Root\-Only*preserves compositional reuse but forces all rollouts to initialize ats0s\_\{0\}, removing frontier continuation, and \(iii\)*Successful\-Only*maintains frontier exploration but restricts recombination to fragments originating from successful trajectories, ignoring useful transitions in failed rollouts\. Additionally, we track*First\-Solve*, the proportion of solved instances whose first verified solution was synthesized via cross\-rollout composition before any complete successful trajectory was observed\. By definition,*First\-Solve*is zero for*No Composition*\(which lacks recombination\) and*Successful\-Only*\(which requires a pre\-existing successful trajectory for fragment reuse\)\. Component Ablations\.Table[3](https://arxiv.org/html/2610.02478#S6.T3)reports ablations for Qwen on Sokoban\. The results show that composition is the main source of improvement\. Disabling it reduces success from58\.4%58\.4\\%to40\.8%40\.8\\%, the largest drop and roughly the level of the strongest baseline, SNR\-Aware \(42\.2%42\.2\\%\), even though the archive and frontier restarts are kept\. Removing frontier restarts \(*Root\-Only*\) reduces success to51\.8%51\.8\\%and*First\-Solve*from31\.6%31\.6\\%to24\.7%24\.7\\%, since every attempt must regenerate known prefixes before exploring new suffixes\. Restricting composition to successful trajectories reduces success to53\.3%53\.3\\%, showing that fragments from failed rollouts remain useful building blocks\. Comparison with Alternative Methods\.We further ask whether stronger success\-oriented objectives or cross\-trajectory credit assignment can matchTropic\. To this end, we compare against MaxRL\([Tajwar et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib15)\), which replaces expected reward with a maximum\-likelihood objective, GiGPO\([Feng et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib12)\), which combines trajectory\- and step\-level advantages, and T\-STAR\([Li et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib24)\), which grafts corrected steps onto shared trajectory structure, instantiated on top of GiGPO\. They reach51\.3%51\.3\\%,47\.6%47\.6\\%, and53\.1%53\.1\\%, respectively, whileTropicreaches58\.4%58\.4\\%,5\.35\.3points above the strongest of them, with the fewest tokens and the shortest training time\.

## 7Conclusion and Discussion

RL has moved from tabular dynamic programming to deep function approximation and now to post\-training large language models\. Each wave changed how values are represented and estimated, but all kept the same objective\. This objective measures how often a sampled attempt succeeds\. Compositional reasoning instead asks which verified solution can be assembled from what the model has already produced\. We showed that answering this question requires only changing the viewpoint of the algebra and herewith a single operation\. Alternative trajectories can be combined by a maximum instead of a sum\. The resulting tropical value names a concrete verified path, never loses a path once found, and splits at any shared state into a best prefix and a best suffix, so solutions can be assembled from fragments that were never sampled together\. Our concrete implementationTropicbuilds on these properties and outperforms the strongest on\-policy baselines on every task and model we test\. We believe this change matters most for self\-improving models\. In particular, such a model must keep what it has verified and build new solutions from old ones\. Transferring this growing set fully into the model’s weights is the natural next step\. Tropical RL asks what can be built from what the model has already found, and we believe this question will define the next wave\.

## Reproducibility statement

In our paper we specifies the environments, and the exact definitions of the metrics and training procedure,[C](https://arxiv.org/html/2610.02478#A3)reports the compute used\. All assumptions behind the theoretical claims are stated formally in[A](https://arxiv.org/html/2610.02478#A1)and each proposition from the main section is proved there\.

### AI use statement

In this work, we used generative AI tools to aid or polish writing, assist with code writing and with parts of the theoretical analysis\. We have not used generative AI tools for retrieval and discovery \(e\.g\., finding related work\)\. All research ideas, including the proposed methods, as well as the core analysis, are original work of the authors\. We have reviewed all AI\-assisted work\. Text and code\.We used OpenAI ChatGPT, Anthropic Claude, Codex, and Claude Code to edit author\-written text and assist with code development\. Mathematical claims\.We used Codex to transcribe images of our handwritten proofs intoLaTeX\. We used ChatGPT and Codex to assist with reviewing proofs throughout the paper\. With Codex, we additionally used the Lean 4 skills package111[https://github\.com/cameronfreer/lean4\-skills](https://github.com/cameronfreer/lean4-skills)\. We subsequently reviewed and refined the analysis through several iterations with AI assistance\. We take responsibility for the final content of this work, including text, claims or artifacts produced with the aid of generative AI\.

## References

- Abdulsalamet al\.\(2026\)A\. Abdulsalam, N\. Patel, and A\. SaxeRL Post\-Training Builds Compositional Reasoning Strategies\.Note:arXiv preprint arXiv:2607\.07646External Links:2607\.07646,[Document](https://dx.doi.org/10.48550/arXiv.2607.07646),[Link](https://arxiv.org/abs/2607.07646)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p1.1)\.
- Akianet al\.\(2008\)M\. Akian, S\. Gaubert, and A\. LakhouaThe Max\-Plus Finite Element Method for Solving Deterministic Optimal Control Problems: Basic Properties and Convergence Analysis\.SIAM Journal on Control and Optimization47\(2\),pp\. 817–848\.External Links:[Document](https://dx.doi.org/10.1137/060655286)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p3.1)\.
- Bach \(2019\)F\. BachMax\-Plus Matching Pursuit for Deterministic Markov Decision Processes\.arXiv preprint arXiv:1906\.08524\.External Links:1906\.08524Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p3.1)\.
- Berthier and Bach \(2020\)E\. Berthier and F\. BachMax\-Plus Linear Approximations for Deterministic Continuous\-State Markov Decision Processes\.IEEE Control Systems Letters4\(3\),pp\. 767–772\.External Links:[Document](https://dx.doi.org/10.1109/LCSYS.2020.2973199)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p3.1)\.
- Brockmanet al\.\(2016\)G\. Brockman, V\. Cheung, L\. Pettersson, J\. Schneider, J\. Schulman, J\. Tang, and W\. ZarembaOpenAI Gym\.External Links:1606\.01540,[Link](https://arxiv.org/abs/1606.01540)Cited by:[§6](https://arxiv.org/html/2610.02478#S6.p1.1)\.
- Brownet al\.\(2024\)B\. Brown, J\. Juravsky, R\. Ehrlich, R\. Clark, Q\. V\. Le, C\. Ré, and A\. MirhoseiniLarge Language Monkeys: Scaling Inference Compute with Repeated Sampling\.Note:arXiv preprint arXiv:2407\.21787External Links:2407\.21787,[Document](https://dx.doi.org/10.48550/arXiv.2407.21787),[Link](https://arxiv.org/abs/2407.21787)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p2.1)\.
- Cuiet al\.\(2025\)G\. Cui, Y\. Zhang, J\. Chen, L\. Yuan, Z\. Wang, Y\. Zuo, H\. Li, Y\. Fan, H\. Chen, W\. Chen, Z\. Liu, H\. Peng, L\. Bai, W\. Ouyang, Y\. Cheng, B\. Zhou, and N\. DingThe Entropy Mechanism of Reinforcement Learning for Reasoning Language Models\.External Links:2505\.22617,[Document](https://dx.doi.org/10.48550/arXiv.2505.22617),[Link](https://arxiv.org/abs/2505.22617)Cited by:[§1](https://arxiv.org/html/2610.02478#S1.p2.1)\.
- DeepSeek\-AIet al\.\(2026\)DeepSeek\-AIet al\.DeepSeek\-V4: Towards Highly Efficient Million\-Token Context Intelligence\.External Links:2606\.19348,[Link](https://arxiv.org/abs/2606.19348)Cited by:[§1](https://arxiv.org/html/2610.02478#S1.p1.1)\.
- Fenget al\.\(2025\)L\. Feng, Z\. Xue, T\. Liu, and B\. AnGroup\-in\-Group Policy Optimization for LLM Agent Training\.External Links:2505\.10978,[Link](https://arxiv.org/abs/2505.10978)Cited by:[§1](https://arxiv.org/html/2610.02478#S1.p1.1),[§5](https://arxiv.org/html/2610.02478#S5.p1.1),[§6\.1](https://arxiv.org/html/2610.02478#S6.SS1.p1.1)\.
- Fu and Liu \(2026\)X\. Fu and W\. LiuReinforcement Learning for Compositional Generalization with Outcome\-Level Optimization\.Note:arXiv preprint arXiv:2605\.04920External Links:2605\.04920,[Document](https://dx.doi.org/10.48550/arXiv.2605.04920),[Link](https://arxiv.org/abs/2605.04920)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p1.1)\.
- Gemma Team \(2026\)Gemma TeamGemma 4 Technical Report\.External Links:2607\.02770,[Link](https://arxiv.org/abs/2607.02770)Cited by:[Appendix C](https://arxiv.org/html/2610.02478#A3.SS0.SSS0.Px1.p1.1),[§6](https://arxiv.org/html/2610.02478#S6.p1.1)\.
- GLM\-5\-Teamet al\.\(2026\)GLM\-5\-Teamet al\.GLM\-5: From Vibe Coding to Agentic Engineering\.External Links:2602\.15763,[Link](https://arxiv.org/abs/2602.15763)Cited by:[§1](https://arxiv.org/html/2610.02478#S1.p1.1)\.
- Gonçalves \(2021\)V\. M\. GonçalvesMax\-Plus Approximation for Reinforcement Learning\.Automatica129,pp\. 109623\.External Links:[Document](https://dx.doi.org/10.1016/j.automatica.2021.109623)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p3.1)\.
- Haarnojaet al\.\(2018\)T\. Haarnoja, A\. Zhou, P\. Abbeel, and S\. LevineSoft Actor\-Critic: Off\-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor\.InInternational Conference on Machine Learning \(ICML\),Cited by:[§4\.1](https://arxiv.org/html/2610.02478#S4.SS1.p1.4)\.
- Jinet al\.\(2026\)R\. Jin, P\. Gao, Y\. Ren, Z\. Han, T\. Zhang, W\. Huang, W\. Liu, J\. Luan, and D\. XiongRevisiting Entropy in Reinforcement Learning for Large Reasoning Models\.InFindings of the Association for Computational Linguistics: ACL 2026,San Diego, California, United States,pp\. 25300–25322\.External Links:[Document](https://dx.doi.org/10.18653/v1/2026.findings-acl.1266),[Link](https://aclanthology.org/2026.findings-acl.1266/)Cited by:[§1](https://arxiv.org/html/2610.02478#S1.p2.1)\.
- Katzet al\.\(2026\)M\. Katz, H\. Kokel, and S\. SreedharanSeemingly Simple Planning Problems Are Computationally Challenging: The Countdown Game\.External Links:2508\.02900,[Link](https://arxiv.org/abs/2508.02900)Cited by:[§6](https://arxiv.org/html/2610.02478#S6.p1.1)\.
- Kazemnejadet al\.\(2024\)A\. Kazemnejad, M\. Aghajohari, E\. Portelance, A\. Sordoni, S\. Reddy, A\. Courville, and N\. L\. RouxVinePPO: Refining Credit Assignment in RL Training of LLMs\.arXiv preprint arXiv:2410\.01679\.Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p1.1)\.
- Keyserset al\.\(2020\)D\. Keysers, N\. Schärli, N\. Scales, H\. Buisman, D\. Furrer, S\. Kashubin, N\. Momchev, D\. Sinopalnikov, L\. Stafiniak, T\. Tihon, D\. Tsarkov, X\. Wang, M\. van Zee, and O\. BousquetMeasuring Compositional Generalization: A Comprehensive Method on Realistic Data\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=SygcCnNKwr)Cited by:[§2](https://arxiv.org/html/2610.02478#S2.p2.1)\.
- Kimi Teamet al\.\(2025\)Kimi Team, A\. Du, B\. Gao, B\. Xing, C\. Jiang, C\. Chen, C\. Li, C\. Xiao, C\. Du, C\. Liao, C\. Tang, C\. Wang, D\. Zhang, E\. Yuan, E\. Lu, F\. Tang, F\. Sung, G\. Wei, G\. Lai, H\. Guo, H\. Zhu, H\. Ding, H\. Hu, H\. Yang, H\. Zhang, H\. Yao, H\. Zhao, H\. Lu, H\. Li, H\. Yu, H\. Gao, H\. Zheng, H\. Yuan, J\. Chen, J\. Guo, J\. Su, J\. Wang, J\. Zhao, J\. Zhang, J\. Liu, J\. Yan, J\. Wu, L\. Shi, L\. Ye, L\. Yu, M\. Dong, N\. Zhang, N\. Ma, Q\. Pan, Q\. Gong, S\. Liu, S\. Ma, S\. Wei, S\. Cao, S\. Huang, T\. Jiang, W\. Gao, W\. Xiong, W\. He, W\. Huang, W\. Xu, W\. Wu, W\. He, X\. Wei, X\. Jia, X\. Wu, X\. Xu, X\. Zu, X\. Zhou, X\. Pan, Y\. Charles, Y\. Li, Y\. Hu, Y\. Liu, Y\. Chen, Y\. Wang, Y\. Liu, Y\. Qin, Y\. Liu, Y\. Yang, Y\. Bao, Y\. Du, Y\. Wu, Y\. Wang, Z\. Zhou, Z\. Wang, Z\. Li, Z\. Zhu, Z\. Zhang, Z\. Wang, Z\. Yang, Z\. Huang, Z\. Huang, Z\. Xu, Z\. Yang, and Z\. LinKimi k1\.5: Scaling Reinforcement Learning with LLMs\.Note:arXiv preprint arXiv:2501\.12599External Links:2501\.12599,[Document](https://dx.doi.org/10.48550/arXiv.2501.12599),[Link](https://arxiv.org/abs/2501.12599)Cited by:[§1](https://arxiv.org/html/2610.02478#S1.p1.1)\.
- Konget al\.\(2026\)L\. Kong, X\. Liu, G\. Chen, M\. Q\. Ma, X\. Song, Y\. Sun, M\. Yurochkin, T\. W\. Killian, R\. Salakhutdinov, K\. Zhang, E\. P\. Xing, and Z\. LiuFrom Reasoning Traces to Reusable Modules: Understanding Compositional Generalization in Language Model Reasoning\.Note:arXiv preprint arXiv:2606\.18089External Links:2606\.18089,[Document](https://dx.doi.org/10.48550/arXiv.2606.18089),[Link](https://arxiv.org/abs/2606.18089)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p1.1)\.
- Lake and Baroni \(2018\)B\. Lake and M\. BaroniGeneralization without Systematicity: On the Compositional Skills of Sequence\-to\-Sequence Recurrent Networks\.InProceedings of the 35th International Conference on Machine Learning,J\. Dy and A\. Krause \(Eds\.\),Proceedings of Machine Learning Research, Vol\.80,pp\. 2873–2882\.External Links:[Link](https://proceedings.mlr.press/v80/lake18a.html)Cited by:[Appendix C](https://arxiv.org/html/2610.02478#A3.SS0.SSS0.Px7.p1.1),[§1](https://arxiv.org/html/2610.02478#S1.p1.1),[§2](https://arxiv.org/html/2610.02478#S2.p2.1)\.
- Liet al\.\(2026\)Y\. Li, S\. Tang, and T\. LanReason in Chains, Learn in Trees: Self\-Rectification and Grafting for Multi\-Turn Agent Policy Optimization\.InFindings of the Association for Computational Linguistics: ACL 2026,pp\. 4673–4686\.External Links:2604\.07165,[Link](https://arxiv.org/abs/2604.07165)Cited by:[§1](https://arxiv.org/html/2610.02478#S1.p1.1),[§5](https://arxiv.org/html/2610.02478#S5.p3.1),[§6\.1](https://arxiv.org/html/2610.02478#S6.SS1.p1.1)\.
- Lightmanet al\.\(2024\)H\. Lightman, V\. Kosaraju, Y\. Burda, H\. Edwards, B\. Baker, T\. Lee, J\. Leike, J\. Schulman, I\. Sutskever, and K\. CobbeLet’s Verify Step by Step\.InInternational Conference on Learning Representations,External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2024/hash/aca97732e30bcf1303bc22ac3924fd16-Abstract-Conference.html)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p1.1)\.
- Liuet al\.\(2026\)H\. Liu, D\. Yu, S\. Lu, Y\. Zhou, R\. Liu, Z\. Liang, H\. Mi, C\. Wei, and D\. YuSave the Good Prefix: Precise Error Penalization via Process\-Supervised RL to Enhance LLM Reasoning\.InFindings of the Association for Computational Linguistics: ACL 2026,pp\. 35450–35477\.Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p3.1)\.
- McEneaney \(2006\)W\. M\. McEneaneyMax\-Plus Methods for Nonlinear Control and Estimation\.Systems and Control: Foundations and Applications,Birkhäuser\.Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p3.1)\.
- Presset al\.\(2023\)O\. Press, M\. Zhang, S\. Min, L\. Schmidt, N\. Smith, and M\. LewisMeasuring and Narrowing the Compositionality Gap in Language Models\.InFindings of the Association for Computational Linguistics: EMNLP 2023,H\. Bouamor, J\. Pino, and K\. Bali \(Eds\.\),Singapore,pp\. 5687–5711\.External Links:[Document](https://dx.doi.org/10.18653/v1/2023.findings-emnlp.378),[Link](https://aclanthology.org/2023.findings-emnlp.378/)Cited by:[§1](https://arxiv.org/html/2610.02478#S1.p1.1),[§2](https://arxiv.org/html/2610.02478#S2.p2.1)\.
- Qwenet al\.\(2025\)Qwen, A\. Yang, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Li, D\. Liu, F\. Huang, H\. Wei, H\. Lin, J\. Yang, J\. Tu, J\. Zhang, J\. Yang, J\. Yang, J\. Zhou, J\. Lin, K\. Dang, K\. Lu, K\. Bao, K\. Yang, L\. Yu, M\. Li, M\. Xue, P\. Zhang, Q\. Zhu, R\. Men, R\. Lin, T\. Li, T\. Tang, T\. Xia, X\. Ren, X\. Ren, Y\. Fan, Y\. Su, Y\. Zhang, Y\. Wan, Y\. Liu, Z\. Cui, Z\. Zhang, and Z\. QiuQwen2\.5 Technical Report\.External Links:2412\.15115,[Link](https://arxiv.org/abs/2412.15115)Cited by:[Appendix C](https://arxiv.org/html/2610.02478#A3.SS0.SSS0.Px1.p1.1),[§6](https://arxiv.org/html/2610.02478#S6.p1.1)\.
- Samantaet al\.\(2026\)A\. Samanta, A\. Magesh, A\. Jain, Y\. Yu, D\. Jiang, K\. Asadi, K\. Hassani, P\. Sajda, J\. Bhandari, and Y\. EfroniCredit Assignment with Resets in Language Model Reasoning\.arXiv preprint arXiv:2605\.25507\.Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p1.1)\.
- Schulmanet al\.\(2018\)J\. Schulman, P\. Moritz, S\. Levine, M\. Jordan, and P\. AbbeelHigh\-Dimensional Continuous Control Using Generalized Advantage Estimation\.External Links:1506\.02438,[Link](https://arxiv.org/abs/1506.02438)Cited by:[Appendix C](https://arxiv.org/html/2610.02478#A3.SS0.SSS0.Px2.p1.1)\.
- Schulmanet al\.\(2017\)J\. Schulman, F\. Wolski, P\. Dhariwal, A\. Radford, and O\. KlimovProximal Policy Optimization Algorithms\.External Links:1707\.06347,[Link](https://arxiv.org/abs/1707.06347)Cited by:[Appendix C](https://arxiv.org/html/2610.02478#A3.SS0.SSS0.Px2.p1.1),[§6](https://arxiv.org/html/2610.02478#S6.p1.1)\.
- Shaoet al\.\(2024\)Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, X\. Bi, H\. Zhang, M\. Zhang, Y\. K\. Li, Y\. Wu, and D\. GuoDeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models\.Note:arXiv preprint arXiv:2402\.03300External Links:2402\.03300,[Document](https://dx.doi.org/10.48550/arXiv.2402.03300),[Link](https://arxiv.org/abs/2402.03300)Cited by:[Appendix C](https://arxiv.org/html/2610.02478#A3.SS0.SSS0.Px2.p1.1),[§6](https://arxiv.org/html/2610.02478#S6.p1.1)\.
- Shenget al\.\(2025\)G\. Sheng, C\. Zhang, Z\. Ye, X\. Wu, W\. Zhang, R\. Zhang, Y\. Peng, H\. Lin, and C\. WuHybridFlow: A Flexible and Efficient RLHF Framework\.InProceedings of the Twentieth European Conference on Computer Systems \(EuroSys\),pp\. 1279–1297\.External Links:[Document](https://dx.doi.org/10.1145/3689031.3696075),[Link](https://doi.org/10.1145/3689031.3696075)Cited by:[Appendix C](https://arxiv.org/html/2610.02478#A3.p1.1)\.
- Tajwaret al\.\(2026\)F\. Tajwar, G\. Zeng, Y\. Zhou, Y\. Song, D\. Arora, Y\. Jiang, J\. Schneider, R\. Salakhutdinov, H\. Feng, and A\. ZanetteMaximum Likelihood Reinforcement Learning\.arXiv preprint arXiv:2602\.02710\.External Links:2602\.02710,[Link](https://arxiv.org/abs/2602.02710)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p2.1),[§6\.1](https://arxiv.org/html/2610.02478#S6.SS1.p1.1)\.
- Tanget al\.\(2025\)Y\. Tang, K\. Zheng, G\. Synnaeve, and R\. MunosOptimizing Language Models for Inference Time Objectives Using Reinforcement Learning\.arXiv preprint arXiv:2503\.19595\.Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p2.1)\.
- Uesatoet al\.\(2022\)J\. Uesato, N\. Kushman, R\. Kumar, F\. Song, N\. Siegel, L\. Wang, A\. Creswell, G\. Irving, and I\. HigginsSolving Math Word Problems with Process\- and Outcome\-Based Feedback\.Note:arXiv preprint arXiv:2211\.14275External Links:2211\.14275,[Document](https://dx.doi.org/10.48550/arXiv.2211.14275),[Link](https://arxiv.org/abs/2211.14275)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p1.1)\.
- Walder and Karkhanis \(2026\)C\. Walder and D\. T\. KarkhanisPass@k Policy Optimization: Solving Harder Reinforcement Learning Problems\.Advances in Neural Information Processing Systems38,pp\. 152416–152445\.Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p2.1)\.
- Wanget al\.\(2026\)Z\. Wang, C\. Gui, X\. Jin, Q\. Wang, L\. Liu, K\. Wang, S\. Chen, L\. Li, Z\. Yang, P\. Zhang, Y\. Lu, J\. Wu, L\. Fei\-Fei, L\. Wang, Y\. Choi, and M\. LiRAGEN\-2: Reasoning Collapse in Agentic RL\.External Links:2604\.06268,[Link](https://arxiv.org/abs/2604.06268)Cited by:[Appendix B](https://arxiv.org/html/2610.02478#A2.p1.1),[Appendix C](https://arxiv.org/html/2610.02478#A3.SS0.SSS0.Px2.p1.1),[Appendix C](https://arxiv.org/html/2610.02478#A3.p1.1),[§1](https://arxiv.org/html/2610.02478#S1.p1.1),[§5](https://arxiv.org/html/2610.02478#S5.p1.1),[§6](https://arxiv.org/html/2610.02478#S6.p1.1)\.
- Weberet al\.\(2018\)T\. Weber, S\. Racanière, D\. P\. Reichert, L\. Buesing, A\. Guez, D\. J\. Rezende, A\. P\. Badia, O\. Vinyals, N\. Heess, Y\. Li, R\. Pascanu, P\. Battaglia, D\. Hassabis, D\. Silver, and D\. WierstraImagination\-Augmented Agents for Deep Reinforcement Learning\.External Links:1707\.06203,[Link](https://arxiv.org/abs/1707.06203)Cited by:[§6](https://arxiv.org/html/2610.02478#S6.p1.1)\.
- Wenet al\.\(2026\)X\. Wen, Z\. Liu, S\. Zheng, S\. Ye, Z\. Wu, Y\. Wang, Z\. Xu, X\. Liang, J\. Li, Z\. Miao, J\. Bian, and M\. YangReinforcement Learning with Verifiable Rewards Implicitly Incentivizes Correct Reasoning in Base LLMs\.InInternational Conference on Learning Representations,External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2026/hash/517f9b9c227b9dd51dba4560f37165ed-Abstract-Conference.html)Cited by:[§1](https://arxiv.org/html/2610.02478#S1.p1.1),[§5](https://arxiv.org/html/2610.02478#S5.p1.1)\.
- Yaoet al\.\(2023a\)S\. Yao, H\. Chen, J\. Yang, and K\. NarasimhanWebShop: Towards Scalable Real\-World Web Interaction with Grounded Language Agents\.External Links:2207\.01206,[Link](https://arxiv.org/abs/2207.01206)Cited by:[§6](https://arxiv.org/html/2610.02478#S6.p1.1)\.
- Yaoet al\.\(2023b\)S\. Yao, D\. Yu, J\. Zhao, I\. Shafran, T\. Griffiths, Y\. Cao, and K\. NarasimhanTree of Thoughts: Deliberate Problem Solving with Large Language Models\.InAdvances in Neural Information Processing Systems,Vol\.36\.External Links:[Document](https://dx.doi.org/10.52202/075280-0517),[Link](https://papers.neurips.cc/paper_files/paper/2023/hash/271db9922b8d1f4dd7aaef84ed5ac703-Abstract-Conference.html)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p3.1)\.
- Yuet al\.\(2025\)Q\. Yu, Z\. Zhang, R\. Zhu, Y\. Yuan, X\. Zuo, Y\. Yue, W\. Dai, T\. Fan, G\. Liu, L\. Liu, X\. Liu, H\. Lin, Z\. Lin, B\. Ma, G\. Sheng, Y\. Tong, C\. Zhang, M\. Zhang, W\. Zhang, H\. Zhu, J\. Zhu, J\. Chen, J\. Chen, C\. Wang, H\. Yu, Y\. Song, X\. Wei, H\. Zhou, J\. Liu, W\. Ma, Y\. Zhang, L\. Yan, M\. Qiao, Y\. Wu, and M\. WangDAPO: An Open\-Source LLM Reinforcement Learning System at Scale\.External Links:2503\.14476,[Link](https://arxiv.org/abs/2503.14476)Cited by:[Appendix C](https://arxiv.org/html/2610.02478#A3.SS0.SSS0.Px2.p1.1),[§5](https://arxiv.org/html/2610.02478#S5.p1.1),[§6](https://arxiv.org/html/2610.02478#S6.p1.1)\.
- Yuanet al\.\(2026\)L\. Yuan, W\. Chen, Y\. Zhang, G\. Cui, H\. Wang, Z\. You, N\. Ding, Z\. Liu, M\. Sun, and H\. PengFromf⁡\(x\)f\(x\)andg⁡\(x\)g\(x\)tof⁡\(g⁡\(x\)\)f\(g\(x\)\): LLMs Learn New Skills in RL by Composing Old Ones\.InInternational Conference on Learning Representations,External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2026/hash/eeae43a68515325cad64c0f54b2d0c70-Abstract-Conference.html)Cited by:[§1](https://arxiv.org/html/2610.02478#S1.p1.1),[§5](https://arxiv.org/html/2610.02478#S5.p1.1)\.
- Yueet al\.\(2025\)Y\. Yue, Z\. Chen, R\. Lu, A\. Zhao, Z\. Wang, Y\. Yue, S\. Song, and G\. HuangDoes Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?\.InAdvances in Neural Information Processing Systems,Vol\.38\.External Links:[Document](https://dx.doi.org/10.52202/085713-1933),[Link](https://papers.nips.cc/paper_files/paper/2025/hash/537d5aa768c2d534016a4d06f87bc8fb-Abstract-Conference.html)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p1.1)\.
- Zhanget al\.\(2024\)D\. Zhang, S\. Zhoubian, Z\. Hu, Y\. Yue, Y\. Dong, and J\. TangReST\-MCTS\*: LLM Self\-Training via Process Reward Guided Tree Search\.InAdvances in Neural Information Processing Systems,Vol\.37\.External Links:[Document](https://dx.doi.org/10.52202/079017-2066),[Link](https://proceedings.neurips.cc/paper_files/paper/2024/hash/76ec4dc30e9faaf0e4b6093eaa377218-Abstract-Conference.html)Cited by:[§5](https://arxiv.org/html/2610.02478#S5.p3.1)\.
- Ziebart \(2010\)B\. D\. ZiebartModeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy\.Ph\.D\. Thesis,Carnegie Mellon University\.Cited by:[§4\.1](https://arxiv.org/html/2610.02478#S4.SS1.p1.4)\.

## Appendix AStructural Results and Proofs

This appendix collects the structural results behind Sections[3](https://arxiv.org/html/2610.02478#S3)–[4\.3](https://arxiv.org/html/2610.02478#S4.SS3)and proves them in full\. The main text established three facts: expected return is not a sufficient statistic for the best witness \(observation[1](https://arxiv.org/html/2610.02478#Thmtheorem1)\), a policy\-indexed value can forget a verified computation, and the requirements of retention force the max–plus semiring \(Proposition\)\. Here we go further in four directions\. We show that the three objectives in our related\-work table are three*distances*from the actor to the set of certified computations, and that the tropical one is the only distance to a*computation*rather than to a distribution over computations \(Section[A\.2](https://arxiv.org/html/2610.02478#A1.SS2)\); this is the result we regard as central, because it turns the choice of algebra into the choice of what the learner is being pulled toward\. We show that the tropical learning signal is the unique one that depends only on which computations have been found and not on how often \(Section[A\.3](https://arxiv.org/html/2610.02478#A1.SS3)\)\. We prove a policy improvement theorem in which training on a single certified path improves the tropical value at every state of the retained graph, with the improvement propagating undamped to interfaces that were never trained from, and we prove that this improvement step is not an expected\-return improvement step and cannot be selected from expected\-return information \(Section[A\.4](https://arxiv.org/html/2610.02478#A1.SS4)\)\. Finally we prove the tropical analogue of the performance difference lemma, derive from it the tropical policy gradient and its lack of visitation weights, and give an exponential\-versus\-logarithmic separation between expected\-return and tropical gradient ascent on a chain \(Section[A\.5](https://arxiv.org/html/2610.02478#A1.SS5)\)\.

One idea organizes all of it\. The tropical value is a functional of a*set*of verified computations, aggregated by a maximum; expected return is a functional of a*measure*over them, aggregated by a sum\. A set grows under discovery and has a most accessible element; a measure is normalized and has only a total\. Every theorem below is a consequence of one of three properties of the maximum that the sum lacks: it is idempotent, it is attained by one of its arguments, and it is insensitive to what happens to its non\-maximal arguments\.

### A\.1Setting and conventions

Throughout, the environment is a finite acyclic computation graph\. A nonterminal statesshas a finite action set𝒜⁡\(s\)\\mathcal\{A\}\(s\)and a deterministic transitionT⁡\(s,a\)T\(s,a\); terminal statesy∈𝒮Ty\\in\\mathcal\{S\}\_\{T\}carry a terminal score, which in the binary case is the boundaryRx​\(y\)∈\{0,−∞\}R\_\{x\}\(y\)\\in\\\{0,\-\\infty\\\}of Section[4](https://arxiv.org/html/2610.02478#S4)\. A*path*fromssis a sequenceτ=\(\(s0,a0\),…,\(sH−1,aH−1\),y\)\\tau=\\big\(\(s\_\{0\},a\_\{0\}\),\\dots,\(s\_\{H\-1\},a\_\{H\-1\}\),y\\big\)withs0=ss\_\{0\}=s,st\+1=T⁡\(st,at\)s\_\{t\+1\}=T\(s\_\{t\},a\_\{t\}\)andy=sH∈𝒮Ty=s\_\{H\}\\in\\mathcal\{S\}\_\{T\}\. Because the graph is acyclic a path visits each state at most once; we writeSτS\_\{\\tau\}for its set of nonterminal states andaτ​\(s\)a\_\{\\tau\}\(s\)for the action it takes ats∈Sτs\\in S\_\{\\tau\}\.Desc⁡\(v\)\\operatorname\{Desc\}\(v\)denotes the set of states reachable fromvv, includingvv, andAnc⁡\(v\)\\operatorname\{Anc\}\(v\)the set of states from whichvvis reachable, excludingvv; acyclicity meansDesc⁡\(v\)∩Anc⁡\(v\)=∅\\operatorname\{Desc\}\(v\)\\cap\\operatorname\{Anc\}\(v\)=\\emptyset\.

An actor is a policyπ\\piwithπ⁡\(a∣s\)\>0\\pi\(a\\mid s\)\>0for all admissibleaa\. It induces the path probabilityPπ¯​\(τ∣s\)=∏tπ⁡\(at∣st\)P\_\{\\bar\{\\pi\}\}\(\\tau\\mid s\)=\\prod\_\{t\}\\pi\(a\_\{t\}\\mid s\_\{t\}\), a probability distribution over the setΩ⁡\(s\)\\Omega\(s\)of complete paths fromss\. When the actor is*tabular softmax*we writeπz​\(a∣s\)=exp⁡\(zs,a\)/∑a′∈𝒜⁡\(s\)exp⁡\(zs,a′\)\\pi\_\{z\}\(a\\mid s\)=\\exp\(z\_\{s,a\}\)/\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\(s\)\}\\exp\(z\_\{s,a^\{\\prime\}\}\)with logitszs,⋅z\_\{s,\\cdot\}that are independent parameters at each state\. We useσ⁡\(z\)=1/\(1\+e−z\)\\sigma\(z\)=1/\(1\+e^\{\-z\}\)for the two\-action case\.

A*certified set*𝒞⁡\(s\)⊆Ω⁡\(s\)\\mathcal\{C\}\(s\)\\subseteq\\Omega\(s\)is a set of paths fromssthat end at terminals withRx=0R\_\{x\}=0; it may be the full set𝒴x\+​\(s\)\\mathcal\{Y\}^\{\+\}\_\{x\}\(s\)or the retained set𝒞t\+​\(s\)\\mathcal\{C\}^\{\+\}\_\{t\}\(s\)of Section[4](https://arxiv.org/html/2610.02478#S4)\. The certified set inherits a graph: its states and edges are those visited by some certified path, and every retained\-graph quantity below is computed on it\. An action of the environment that is admissible atssbut leads to no certified terminal is treated as an edge to a rejected terminal, with value−∞\-\\infty; this lets the softmax range over all of𝒜⁡\(s\)\\mathcal\{A\}\(s\)while the dynamic program ranges over certified structure, and it is exactly how TROPIC’s retained graph is used\.

Path scores are additive with the accessibility weightλ\>0\\lambda\>0and the internal rewardrr:w⁡\(s,a\)=λ​log⁡π⁡\(a∣s\)\+r⁡\(s,a\)w\(s,a\)=\\lambda\\log\\pi\(a\\mid s\)\+r\(s,a\)andWπ​\(τ\)=∑tw⁡\(st,at\)\+g⁡\(y\)W\_\{\\pi\}\(\\tau\)=\\sum\_\{t\}w\(s\_\{t\},a\_\{t\}\)\+g\(y\)withg⁡\(y\)g\(y\)the terminal score\. In Sections[A\.2](https://arxiv.org/html/2610.02478#A1.SS2)–[A\.4](https://arxiv.org/html/2610.02478#A1.SS4)we takeλ=1\\lambda=1,r≡0r\\equiv 0and the binary boundary, so thatWπ​\(τ\)=log⁡Pπ¯​\(τ∣s\)W\_\{\\pi\}\(\\tau\)=\\log P\_\{\\bar\{\\pi\}\}\(\\tau\\mid s\)for certifiedτ\\tau; Section[A\.5](https://arxiv.org/html/2610.02478#A1.SS5)keepsλ\\lambdaandrrgeneral\. The tropical valuesQtropπ¯,Vtropπ¯,Atropπ¯Q^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\},V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\},A^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}are those of Equation equation[6](https://arxiv.org/html/2610.02478#S4.E6); when the actor is clear from context we drop the superscript, and we writeV′V^\{\\prime\},w′w^\{\\prime\}for quantities under an updated actor\. The conventionmax⁡∅=−∞\\max\\emptyset=\-\\inftyis in force, and any sum containing−∞\-\\inftyequals−∞\-\\infty\.

### A\.2Three projections onto the certified set

The main text compares expected return, maximum likelihood and the tropical value by the operation each uses to aggregate verified paths: sum, log\-sum\-exp, max\. That comparison is algebraic\. There is an equivalent geometric comparison that is more revealing, because it says what each objective is pulling the actor toward\. Fix a statess, the actor’s path distributionP=Pπ¯\(⋅∣s\)P=P\_\{\\bar\{\\pi\}\}\(\\cdot\\mid s\)onΩ⁡\(s\)\\Omega\(s\), and a certified set𝒞=𝒞⁡\(s\)\\mathcal\{C\}=\\mathcal\{C\}\(s\)\. The set of all distributions supported on𝒞\\mathcal\{C\}is a simplexΔ⁡\(𝒞\)\\Delta\(\\mathcal\{C\}\); its vertices are the point massesδτ\\delta\_\{\\tau\}, one per certified path, and each vertex is a*deterministic policy that executes one certified computation*\. The three objectives are the actor’s distance to this simplex measured three ways\.

###### Lemma 5\(Variational identities\)\.

LetPPbe a probability distribution on a finite setΩ\\OmegawithP⁡\(ω\)\>0P\(\\omega\)\>0for allω\\omega, and let𝒞⊆Ω\\mathcal\{C\}\\subseteq\\Omegabe nonempty\. Writeq⋆=P\(⋅∣𝒞\)q^\{\\star\}=P\(\\cdot\\mid\\mathcal\{C\}\)for the conditional ofPPon𝒞\\mathcal\{C\}andτ⋆∈arg⁡maxτ∈𝒞⁡P⁡\(τ\)\\tau^\{\\star\}\\in\\arg\\max\_\{\\tau\\in\\mathcal\{C\}\}P\(\\tau\)\. Then

1. \(i\)minq∈Δ⁡\(𝒞\)DKL\(q∥P\)=−logP\(𝒞\)\\displaystyle\\min\_\{q\\in\\Delta\(\\mathcal\{C\}\)\}D\_\{\\mathrm\{KL\}\}\(q\\,\\\|\\,P\)=\-\\log P\(\\mathcal\{C\}\), attained uniquely atq=q⋆q=q^\{\\star\};
2. \(ii\)minτ∈𝒞DKL\(δτ∥P\)=−maxτ∈𝒞logP\(τ\)\\displaystyle\\min\_\{\\tau\\in\\mathcal\{C\}\}D\_\{\\mathrm\{KL\}\}\(\\delta\_\{\\tau\}\\,\\\|\\,P\)=\-\\max\_\{\\tau\\in\\mathcal\{C\}\}\\log P\(\\tau\), attained exactly at the maximizers ofPPon𝒞\\mathcal\{C\};
3. \(iii\)maxτ∈𝒞⁡log⁡P⁡\(τ\)=log⁡P⁡\(𝒞\)\+log⁡q⋆​\(τ⋆\)\\displaystyle\\max\_\{\\tau\\in\\mathcal\{C\}\}\\log P\(\\tau\)=\\log P\(\\mathcal\{C\}\)\+\\log q^\{\\star\}\(\\tau^\{\\star\}\)\.

Consequently, withP=Pπ¯\(⋅∣s\)P=P\_\{\\bar\{\\pi\}\}\(\\cdot\\mid s\)and𝒞=𝒞⁡\(s\)\\mathcal\{C\}=\\mathcal\{C\}\(s\),

Vπ¯\(s\)=P\(𝒞\),logVπ¯\(s\)=−minq∈Δ⁡\(𝒞\)DKL\(q∥P\),Vtropπ¯\(s\)=−minτ∈𝒞DKL\(δτ∥P\),V^\{\\bar\{\\pi\}\}\(s\)=P\(\\mathcal\{C\}\),\\qquad\\log V^\{\\bar\{\\pi\}\}\(s\)=\-\\min\_\{q\\in\\Delta\(\\mathcal\{C\}\)\}D\_\{\\mathrm\{KL\}\}\(q\\,\\\|\\,P\),\\qquad V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s\)=\-\\min\_\{\\tau\\in\\mathcal\{C\}\}D\_\{\\mathrm\{KL\}\}\(\\delta\_\{\\tau\}\\,\\\|\\,P\),\(15\)and the gap between the last two isVtropπ¯​\(s\)−log⁡Vπ¯​\(s\)=log⁡q⋆​\(τ⋆∣s\)≤0V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s\)\-\\log V^\{\\bar\{\\pi\}\}\(s\)=\\log q^\{\\star\}\(\\tau^\{\\star\}\\mid s\)\\leq 0, the log posterior share of the best witness among the actor’s successes fromss\.

###### Proof\.

\(i\) Forq∈Δ⁡\(𝒞\)q\\in\\Delta\(\\mathcal\{C\}\)every term of the divergence withq⁡\(τ\)=0q\(\\tau\)=0vanishes, soDKL\(q∥P\)=∑τ∈𝒞q\(τ\)logq⁡\(τ\)P⁡\(τ\)D\_\{\\mathrm\{KL\}\}\(q\\\|P\)=\\sum\_\{\\tau\\in\\mathcal\{C\}\}q\(\\tau\)\\log\\frac\{q\(\\tau\)\}\{P\(\\tau\)\}\. SinceP⁡\(τ\)=q⋆​\(τ\)​P​\(𝒞\)P\(\\tau\)=q^\{\\star\}\(\\tau\)P\(\\mathcal\{C\}\)forτ∈𝒞\\tau\\in\\mathcal\{C\},

DKL\(q∥P\)=∑τ∈𝒞q\(τ\)logq⁡\(τ\)q⋆​\(τ\)\+∑τ∈𝒞q\(τ\)log1P⁡\(𝒞\)=DKL\(q∥q⋆\)−logP\(𝒞\)\.D\_\{\\mathrm\{KL\}\}\(q\\\|P\)=\\sum\_\{\\tau\\in\\mathcal\{C\}\}q\(\\tau\)\\log\\frac\{q\(\\tau\)\}\{q^\{\\star\}\(\\tau\)\}\+\\sum\_\{\\tau\\in\\mathcal\{C\}\}q\(\\tau\)\\log\\frac\{1\}\{P\(\\mathcal\{C\}\)\}=D\_\{\\mathrm\{KL\}\}\(q\\\|q^\{\\star\}\)\-\\log P\(\\mathcal\{C\}\)\.The first term is nonnegative and vanishes exactly whenq=q⋆q=q^\{\\star\}, which gives the minimum and its uniqueness\. \(ii\)DKL\(δτ∥P\)=1⋅log1P⁡\(τ\)=−logP\(τ\)D\_\{\\mathrm\{KL\}\}\(\\delta\_\{\\tau\}\\\|P\)=1\\cdot\\log\\frac\{1\}\{P\(\\tau\)\}=\-\\log P\(\\tau\), so minimizing overτ∈𝒞\\tau\\in\\mathcal\{C\}is maximizinglog⁡P⁡\(τ\)\\log P\(\\tau\)\. \(iii\)q⋆​\(τ⋆\)=P⁡\(τ⋆\)/P⁡\(𝒞\)q^\{\\star\}\(\\tau^\{\\star\}\)=P\(\\tau^\{\\star\}\)/P\(\\mathcal\{C\}\); take logarithms\. The identifications in equation[15](https://arxiv.org/html/2610.02478#A1.E15)are the definitions ofVπ¯V^\{\\bar\{\\pi\}\}and, by Equation equation[8](https://arxiv.org/html/2610.02478#S4.E8), ofVtropπ¯V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}under the binary boundary withλ=1\\lambda=1; the gap is \(iii\)\. Sinceq⋆q^\{\\star\}is a probability,log⁡q⋆​\(τ⋆\)≤0\\log q^\{\\star\}\(\\tau^\{\\star\}\)\\leq 0\. ∎

The lemma says that expected return measures how much of the actor’s mass already lies on certified computations; maximum likelihood measures how far the actor is from the*nearest distribution over*certified computations; the tropical value measures how far the actor is from the*nearest certified computation*\. The gap term quantifies the difference between the last two: it is zero precisely when all of the actor’s success mass atssis concentrated on one path, and it is the information Propositionshows expected return cannot supply\. The three are related by exponentiation and by adding the gap, so nothing is lost in the identities; what differs is the*minimizer*, which is the object learning moves toward\. For the hull distance it is the posteriorq⋆q^\{\\star\}, a distribution; for the vertex distance it is a path\.

We now show that if one asks the value to describe a path, and asks it never to decrease when a certified path is added, then the aggregation is forced to be the maximum\. This is a second route to Proposition, and the two hypotheses are exactly the two operational requirements of the system in Section[4\.3](https://arxiv.org/html/2610.02478#S4.SS3): the value must refer to something that can be replayed, composed and verified, and the archive must never lose what it has certified\.

###### Definition 1\(Aggregation; certification; retention\)\.

An*aggregation*is a commutative and associative binary operation⊕:ℝ×ℝ→ℝ\\oplus:\\mathbb\{R\}\\times\\mathbb\{R\}\\to\\mathbb\{R\}\. For a finite nonempty multisetAAof reals we write⨁A\\bigoplus Afor the iterated operation, which is well defined by commutativity and associativity, and we set⨁∅=−∞\\bigoplus\\emptyset=\-\\infty\. Given path scores, the induced value isV⊕​\(s\)=⨁\{W⁡\(τ\):τ∈𝒞⁡\(s\)\}V\_\{\\oplus\}\(s\)=\\bigoplus\\\{W\(\\tau\):\\tau\\in\\mathcal\{C\}\(s\)\\\}\. We consider three properties\.

- \(Cont\)⊕\\oplusis continuous onℝ2\\mathbb\{R\}^\{2\}\.
- \(Cert\)⊕\\oplusis*selective*:a⊕b∈\{a,b\}a\\oplus b\\in\\\{a,b\\\}for alla,b∈ℝa,b\\in\\mathbb\{R\}\. By induction,⨁A∈A\\bigoplus A\\in Afor every finite nonempty multiset: the value of a state is the score of one of its certified continuations\.
- \(Ret\)Adding a continuation never lowers the value:⨁\(A⊎\{c\}\)≥⨁A\\bigoplus\(A\\uplus\\\{c\\\}\)\\geq\\bigoplus Afor every finite multisetAAand everyc∈ℝc\\in\\mathbb\{R\}\.

###### Theorem 6\(Certification and retention force the tropical value\)\.

An aggregation satisfying\(Cont\),\(Cert\)and\(Ret\)is the maximum:a⊕b=max⁡\{a,b\}a\\oplus b=\\max\\\{a,b\\\}for alla,ba,b\. Conversely the maximum satisfies all three\. Consequently, with the additive scores of Equation equation[2](https://arxiv.org/html/2610.02478#S3.E2), the induced value is the tropical valueV⊕=Vtropπ¯V\_\{\\oplus\}=V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}of Equation equation[6](https://arxiv.org/html/2610.02478#S4.E6), and by Lemma[5](https://arxiv.org/html/2610.02478#Thmtheorem5)it is the negative KL distance from the actor to the nearest certified vertex\.

###### Proof\.

LetU=\{\(a,b\)∈ℝ2:a\>b\}U=\\\{\(a,b\)\\in\\mathbb\{R\}^\{2\}:a\>b\\\}, an open half\-plane and therefore a connected set\. Define

F1=\{\(a,b\)∈U:a⊕b=a\},F2=\{\(a,b\)∈U:a⊕b=b\}\.F\_\{1\}=\\\{\(a,b\)\\in U:\\ a\\oplus b=a\\\},\\qquad F\_\{2\}=\\\{\(a,b\)\\in U:\\ a\\oplus b=b\\\}\.By \(Cont\) the maps\(a,b\)↦a⊕b−a\(a,b\)\\mapsto a\\oplus b\-aand\(a,b\)↦a⊕b−b\(a,b\)\\mapsto a\\oplus b\-bare continuous, soF1F\_\{1\}andF2F\_\{2\}are closed subsets ofUU\. By \(Cert\),F1∪F2=UF\_\{1\}\\cup F\_\{2\}=U\. OnUUwe havea≠ba\\neq b, soF1∩F2=∅F\_\{1\}\\cap F\_\{2\}=\\emptyset\. A connected set cannot be written as the disjoint union of two nonempty closed subsets, henceF1=UF\_\{1\}=UorF2=UF\_\{2\}=U\.

SupposeF1=UF\_\{1\}=U\. Thena⊕b=a=max⁡\{a,b\}a\\oplus b=a=\\max\\\{a,b\\\}whenevera\>ba\>b\. Fora<ba<b, commutativity givesa⊕b=b⊕a=b=max⁡\{a,b\}a\\oplus b=b\\oplus a=b=\\max\\\{a,b\\\}\. On the diagonal \(Cert\) givesa⊕a=aa\\oplus a=a\. So⊕=max\\oplus=\\max\.

Suppose insteadF2=UF\_\{2\}=U\. The same argument gives⊕=min\\oplus=\\min\. But then \(Ret\) fails: forA=\{a\}A=\\\{a\\\}andc<ac<a,⨁\(A⊎\{c\}\)=min⁡\{a,c\}=c<a=⨁A\\bigoplus\(A\\uplus\\\{c\\\}\)=\\min\\\{a,c\\\}=c<a=\\bigoplus A\. Hence this case is excluded and⊕=max\\oplus=\\max\.

Converselymax\\maxis continuous, commutative, associative, selective, andmax⁡\(A⊎\{c\}\)≥max⁡A\\max\(A\\uplus\\\{c\\\}\)\\geq\\max A\. With additive scores,Vmax​\(s\)=maxτ∈𝒞⁡\(s\)⁡W⁡\(τ\)V\_\{\\max\}\(s\)=\\max\_\{\\tau\\in\\mathcal\{C\}\(s\)\}W\(\\tau\), which is the path form of Equation equation[6](https://arxiv.org/html/2610.02478#S4.E6)under the binary boundary, and the last claim is Lemma[5](https://arxiv.org/html/2610.02478#Thmtheorem5)\(ii\)\. ∎

The proof is short, and it is worth being clear about where the content lies\. \(Cont\) and commutativity are hygiene: values should vary continuously with accessibilities and should not depend on the order in which continuations are listed\. The two substantive hypotheses each eliminate one candidate\. Certification eliminates every soft aggregation, because a soft aggregate of two different scores lies strictly between or above them and is the score of nothing; retention eliminates the minimum, the only other selective candidate\. What survives is the maximum, and with it the witness, idempotence, and distributivity\. The next proposition records which familiar aggregations fail which hypothesis; the point is not that they are wrong, but that each is the right value for a different question\.

###### Proposition 2\(Which aggregations fail which hypothesis\)\.

1. \(i\)LSE⁡\(a,b\)=log⁡\(ea\+eb\)\\LSE\(a,b\)=\\log\(e^\{a\}\+e^\{b\}\), the aggregation of maximum likelihood, satisfies\(Cont\), commutativity, associativity and\(Ret\), and fails\(Cert\)\.
2. \(ii\)Addition of probabilitiesp⊕q=p\+qp\\oplus q=p\+q, the aggregation of expected return on the probability scale, satisfies\(Ret\)and fails\(Cert\)\.
3. \(iii\)The minimum satisfies\(Cont\),\(Cert\), commutativity and associativity, and fails\(Ret\)\.
4. \(iv\)No policy\-indexed value satisfies the dynamic form of\(Ret\): by Proposition[1](https://arxiv.org/html/2610.02478#Thmproposition1), such a value can strictly decrease on a state all of whose certified continuations remain certified\.

###### Proof\.

\(i\)LSE\\LSEis continuous, symmetric, and associative sinceLSE⁡\(LSE⁡\(a,b\),c\)=log⁡\(ea\+eb\+ec\)\\LSE\(\\LSE\(a,b\),c\)=\\log\(e^\{a\}\+e^\{b\}\+e^\{c\}\)\. For⨁\(A⊎\{c\}\)=log\(∑a∈Aea\+ec\)\>log∑a∈Aea\\bigoplus\(A\\uplus\\\{c\\\}\)=\\log\\big\(\\sum\_\{a\\in A\}e^\{a\}\+e^\{c\}\\big\)\>\\log\\sum\_\{a\\in A\}e^\{a\}, so \(Ret\) holds\. For anya,ba,b,LSE⁡\(a,b\)\>max⁡\{a,b\}\\LSE\(a,b\)\>\\max\\\{a,b\\\}becauseea\+eb\>emax⁡\{a,b\}e^\{a\}\+e^\{b\}\>e^\{\\max\\\{a,b\\\}\}; henceLSE⁡\(a,b\)∉\{a,b\}\\LSE\(a,b\)\\notin\\\{a,b\\\}and \(Cert\) fails\. \(ii\)p\+q≥pp\+q\\geq p, so \(Ret\) holds;p\+q∉\{p,q\}p\+q\\notin\\\{p,q\\\}whenp,q\>0p,q\>0, so \(Cert\) fails\. \(iii\)min⁡\{a,b\}∈\{a,b\}\\min\\\{a,b\\\}\\in\\\{a,b\\\}, continuity and the algebraic identities are immediate; the failure of \(Ret\) was shown in the proof of Theorem[6](https://arxiv.org/html/2610.02478#Thmtheorem6)\. \(iv\) is Proposition[1](https://arxiv.org/html/2610.02478#Thmproposition1)\. ∎

The consequences of the maximum that the rest of this appendix uses are collected next\. The first is the distributivity that makes composition a local operation; the second is the fact that the gradient of a maximum is the gradient of its maximizer; the third is that the value can be certified by one verifier call\. Each is elementary; what matters is that each is available*because*of Theorem[6](https://arxiv.org/html/2610.02478#Thmtheorem6)and unavailable under any soft aggregation\.

###### Corollary 1\(Consequences of the maximum\)\.

LetV⁡\(s\)=maxτ∈𝒞⁡\(s\)⁡W⁡\(τ\)V\(s\)=\\max\_\{\\tau\\in\\mathcal\{C\}\(s\)\}W\(\\tau\)with additive scores\.

1. \(a\)\(Optimal substructure\.\)Ifτ=p∘q\\tau=p\\circ qattainsV⁡\(s\)V\(s\)andqqstarts atvv, thenqqattainsV⁡\(v\)V\(v\)\. Consequently, for the set𝒫⁡\(v\)\\mathcal\{P\}\(v\)of certified prefixes fromsstovvand the set𝒞⁡\(v\)\\mathcal\{C\}\(v\)of certified suffixes fromvv,maxp∈𝒫⁡\(v\),q∈𝒞⁡\(v\)⁡W⁡\(p∘q\)=maxp⁡W⁡\(p\)\+maxq⁡W⁡\(q\)\\max\_\{p\\in\\mathcal\{P\}\(v\),\\,q\\in\\mathcal\{C\}\(v\)\}W\(p\\circ q\)=\\max\_\{p\}W\(p\)\+\\max\_\{q\}W\(q\), which is Equation equation[9](https://arxiv.org/html/2610.02478#S4.E9)\.
2. \(b\)\(Gradient of the maximum\.\)Let the scores depend on a parameterθ∈ℝn\\theta\\in\\mathbb\{R\}^\{n\}through continuously differentiable functionsθ↦Wθ​\(τ\)\\theta\\mapsto W\_\{\\theta\}\(\\tau\), and suppose that atθ0\\theta\_\{0\}the maximizerτ⋆\\tau^\{\\star\}over𝒞⁡\(s\)\\mathcal\{C\}\(s\)is unique\. Thenθ↦Vθ​\(s\)\\theta\\mapsto V\_\{\\theta\}\(s\)is continuously differentiable on a neighbourhood ofθ0\\theta\_\{0\}and∇θVθ0​\(s\)=∇θWθ0​\(τ⋆\)\\nabla\_\{\\theta\}V\_\{\\theta\_\{0\}\}\(s\)=\\nabla\_\{\\theta\}W\_\{\\theta\_\{0\}\}\(\\tau^\{\\star\}\)\. ForWθ​\(τ\)=log⁡Pθ​\(τ∣s\)W\_\{\\theta\}\(\\tau\)=\\log P\_\{\\theta\}\(\\tau\\mid s\)this is the score function of the witness,∑\(st,at\)∈τ⋆∇θ​log​πθ​\(at∣st\)\\sum\_\{\(s\_\{t\},a\_\{t\}\)\\in\\tau^\{\\star\}\}\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(a\_\{t\}\\mid s\_\{t\}\)\.
3. \(c\)\(One\-call certificate\.\)IfV⁡\(s\)\>−∞V\(s\)\>\-\\inftythere is a pathτ⋆\\tau^\{\\star\}withW⁡\(τ⋆\)=V⁡\(s\)W\(\\tau^\{\\star\}\)=V\(s\); replayingτ⋆\\tau^\{\\star\}and querying the verifier once confirms that the terminal is accepted, and the score of the replayed path equals the value\. No finite number of verifier calls on individual paths determineslog⁡Vπ¯​\(s\)\\log V^\{\\bar\{\\pi\}\}\(s\)without knowledge of the probabilities of all paths in𝒞⁡\(s\)\\mathcal\{C\}\(s\)\.

###### Proof\.

\(a\) Supposeq′q^\{\\prime\}is a certified suffix fromvvwithW⁡\(q′\)\>W⁡\(q\)W\(q^\{\\prime\}\)\>W\(q\)\. Thenp∘q′p\\circ q^\{\\prime\}is a certified path fromssand, by additivity,W⁡\(p∘q′\)=W⁡\(p\)\+W⁡\(q′\)\>W⁡\(p\)\+W⁡\(q\)=W⁡\(τ\)=V⁡\(s\)W\(p\\circ q^\{\\prime\}\)=W\(p\)\+W\(q^\{\\prime\}\)\>W\(p\)\+W\(q\)=W\(\\tau\)=V\(s\), contradicting thatτ\\tauattains the maximum\. HenceW⁡\(q\)=maxq′⁡W⁡\(q′\)=V⁡\(v\)W\(q\)=\\max\_\{q^\{\\prime\}\}W\(q^\{\\prime\}\)=V\(v\)\. For the second claim, additivity givesW⁡\(p∘q\)=W⁡\(p\)\+W⁡\(q\)W\(p\\circ q\)=W\(p\)\+W\(q\)for every compatible pair, and the maximum of a sum of independent terms is the sum of the maxima:maxp,q⁡\[W⁡\(p\)\+W⁡\(q\)\]≤maxp⁡W⁡\(p\)\+maxq⁡W⁡\(q\)\\max\_\{p,q\}\[W\(p\)\+W\(q\)\]\\leq\\max\_\{p\}W\(p\)\+\\max\_\{q\}W\(q\)termwise, and the pair of maximizers attains the right\-hand side\.

\(b\) Writefτ​\(θ\)=Wθ​\(τ\)f\_\{\\tau\}\(\\theta\)=W\_\{\\theta\}\(\\tau\)forτ∈𝒞⁡\(s\)\\tau\\in\\mathcal\{C\}\(s\), finitely many continuously differentiable functions\. By uniqueness,ε:=fτ⋆​\(θ0\)−maxτ≠τ⋆⁡fτ​\(θ0\)\>0\\varepsilon:=f\_\{\\tau^\{\\star\}\}\(\\theta\_\{0\}\)\-\\max\_\{\\tau\\neq\\tau^\{\\star\}\}f\_\{\\tau\}\(\\theta\_\{0\}\)\>0\. By continuity of finitely many functions there is a neighbourhoodNNofθ0\\theta\_\{0\}on which\|fτ​\(θ\)−fτ​\(θ0\)\|<ε/2\|f\_\{\\tau\}\(\\theta\)\-f\_\{\\tau\}\(\\theta\_\{0\}\)\|<\\varepsilon/2for allτ\\tau; onNN,fτ⋆​\(θ\)\>fτ​\(θ\)f\_\{\\tau^\{\\star\}\}\(\\theta\)\>f\_\{\\tau\}\(\\theta\)for everyτ≠τ⋆\\tau\\neq\\tau^\{\\star\}, henceVθ​\(s\)=fτ⋆​\(θ\)V\_\{\\theta\}\(s\)=f\_\{\\tau^\{\\star\}\}\(\\theta\)onNNand the differentiability claim follows\. For log\-likelihood scores,∇θ​log​Pθ​\(τ⋆∣s\)=∑t∇θ​log​πθ​\(at∣st\)\\nabla\_\{\\theta\}\\log P\_\{\\theta\}\(\\tau^\{\\star\}\\mid s\)=\\sum\_\{t\}\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(a\_\{t\}\\mid s\_\{t\}\)by the autoregressive factorization equation[2](https://arxiv.org/html/2610.02478#S3.E2)\.

\(c\) The maximum over a finite nonempty set is attained; takeτ⋆\\tau^\{\\star\}a maximizer\. Its terminal is accepted becauseW⁡\(τ⋆\)\>−∞W\(\\tau^\{\\star\}\)\>\-\\inftyrequiresRx​\(y\)=0R\_\{x\}\(y\)=0\. For the last claim,logVπ¯\(s\)=log∑τ∈𝒞⁡\(s\)P\(τ∣s\)\\log V^\{\\bar\{\\pi\}\}\(s\)=\\log\\sum\_\{\\tau\\in\\mathcal\{C\}\(s\)\}P\(\\tau\\mid s\)depends on every summand, and two certified sets with the same verified paths queried and different unqueried probabilities give different values\. ∎

### A\.3Frequency\-free learning signals

Proposition[1](https://arxiv.org/html/2610.02478#Thmproposition1)located the cause of forgetting in normalization: probability granted to one computation is taken from another\. A related cause of collapse is*frequency bias*: in on\-policy learning the weight a computation receives in the update is its sampling probability, so computations that are found often are reinforced more, are then found more often, and so on\. One would like a learning signal that depends on*which*computations have been discovered but not on*how many times*\. This section shows that this requirement is exactly idempotence of the aggregation, hence, by Theorem[6](https://arxiv.org/html/2610.02478#Thmtheorem6), exactly the maximum\.

###### Definition 2\(Frequency\-free aggregation\)\.

Let⊕\\oplusbe an aggregation as in Definition[1](https://arxiv.org/html/2610.02478#Thmdefinition1)\. For a finite multisetAAletsupp⁡\(A\)\\operatorname\{supp\}\(A\)be the set of its distinct elements\.⊕\\oplusis*frequency\-free*if⨁A=⨁supp⁡\(A\)\\bigoplus A=\\bigoplus\\operatorname\{supp\}\(A\)for every finite nonempty multisetAA\. It is*idempotent*ifa⊕a=aa\\oplus a=afor allaa\.

###### Theorem 7\(Frequency\-free if and only if idempotent\)\.

An aggregation is frequency\-free if and only if it is idempotent\. In particular the maximum is frequency\-free, whileLSE\\LSEand addition are not\.

###### Proof\.

Suppose⊕\\oplusis frequency\-free\. For the multisetA=\{a,a\}A=\\\{a,a\\\}we havesupp⁡\(A\)=\{a\}\\operatorname\{supp\}\(A\)=\\\{a\\\}, soa⊕a=⨁A=⨁\{a\}=aa\\oplus a=\\bigoplus A=\\bigoplus\\\{a\\\}=a:⊕\\oplusis idempotent\.

Suppose⊕\\oplusis idempotent\. For a finite nonempty multisetAAletn⁡\(A\)=\|A\|−\|supp⁡\(A\)\|≥0n\(A\)=\|A\|\-\|\\operatorname\{supp\}\(A\)\|\\geq 0count its repetitions\. We show⨁A=⨁supp⁡\(A\)\\bigoplus A=\\bigoplus\\operatorname\{supp\}\(A\)by induction onn⁡\(A\)n\(A\)\. Ifn⁡\(A\)=0n\(A\)=0thenAAis a set and there is nothing to prove\. Ifn⁡\(A\)≥1n\(A\)\\geq 1, some elementaaoccurs at least twice, and we may writeA=\{a,a\}⊎A′A=\\\{a,a\\\}\\uplus A^\{\\prime\}for a multisetA′A^\{\\prime\}\. IfA′=∅A^\{\\prime\}=\\emptysetthen⨁A=a⊕a=a=⨁\{a\}=⨁supp⁡\(A\)\\bigoplus A=a\\oplus a=a=\\bigoplus\\\{a\\\}=\\bigoplus\\operatorname\{supp\}\(A\)\. Otherwise, using commutativity and associativity to group the two copies,

⨁A=\(a⊕a\)⊕⨁A′=a⊕⨁A′=⨁\(\{a\}⊎A′\)\.\\bigoplus A=\(a\\oplus a\)\\oplus\\bigoplus A^\{\\prime\}=a\\oplus\\bigoplus A^\{\\prime\}=\\bigoplus\(\\\{a\\\}\\uplus A^\{\\prime\}\)\.The multiset\{a\}⊎A′\\\{a\\\}\\uplus A^\{\\prime\}has the same support asAAandn⁡\(\{a\}⊎A′\)=n⁡\(A\)−1n\(\\\{a\\\}\\uplus A^\{\\prime\}\)=n\(A\)\-1, so by the induction hypothesis its aggregate is⨁supp⁡\(A\)\\bigoplus\\operatorname\{supp\}\(A\)\.

Finallymax⁡\{a,a\}=a\\max\\\{a,a\\\}=a, whereasLSE⁡\(a,a\)=a\+log⁡2≠a\\LSE\(a,a\)=a\+\\log 2\\neq aanda\+a=2​a≠aa\+a=2a\\neq afora≠0a\\neq 0\. ∎

The theorem is a statement about values\. Its bearing on learning is through the gradient: if the value is a function of the support only, so is its gradient wherever it exists\. The next proposition computes the gradients of the three objectives on a multiset of certified paths and makes the contrast concrete\. It is the appendix form of Equation equation\.

###### Proposition 3\(The weights of the three objectives\)\.

LetAAbe a finite multiset of certified paths froms0​\(x\)s\_\{0\}\(x\)with scoresWθ​\(τ\)=log⁡Pθ​\(τ∣x\)W\_\{\\theta\}\(\\tau\)=\\log P\_\{\\theta\}\(\\tau\\mid x\), continuously differentiable inθ\\theta\. Define

JERA\(θ\)=∑τ∈AeWθ​\(τ\),JMLA\(θ\)=log∑τ∈AeWθ​\(τ\),JtropA\(θ\)=maxτ∈AWθ\(τ\),J\_\{\\mathrm\{ER\}\}^\{A\}\(\\theta\)=\\sum\_\{\\tau\\in A\}e^\{W\_\{\\theta\}\(\\tau\)\},\\qquad J\_\{\\mathrm\{ML\}\}^\{A\}\(\\theta\)=\\log\\sum\_\{\\tau\\in A\}e^\{W\_\{\\theta\}\(\\tau\)\},\\qquad J\_\{\\mathrm\{trop\}\}^\{A\}\(\\theta\)=\\max\_\{\\tau\\in A\}W\_\{\\theta\}\(\\tau\),where sums run over the multiset with multiplicity\. Then each gradient has the form∑τ∈Aω⁡\(τ\)​∇θ​log⁡Pθ​\(τ∣x\)\\sum\_\{\\tau\\in A\}\\omega\(\\tau\)\\nabla\_\{\\theta\}\\log P\_\{\\theta\}\(\\tau\\mid x\)with

ωER\(τ\)=Pθ\(τ∣x\),ωML\(τ\)=Pθ​\(τ∣x\)∑τ′∈APθ​\(τ′∣x\),ωtrop\(τ\)=𝟏\{τ=τ⋆\},\\omega\_\{\\mathrm\{ER\}\}\(\\tau\)=P\_\{\\theta\}\(\\tau\\mid x\),\\qquad\\omega\_\{\\mathrm\{ML\}\}\(\\tau\)=\\frac\{P\_\{\\theta\}\(\\tau\\mid x\)\}\{\\sum\_\{\\tau^\{\\prime\}\\in A\}P\_\{\\theta\}\(\\tau^\{\\prime\}\\mid x\)\},\\qquad\\omega\_\{\\mathrm\{trop\}\}\(\\tau\)=\\mathbf\{1\}\\\{\\tau=\\tau^\{\\star\}\\\},the last wherever the maximizerτ⋆\\tau^\{\\star\}is unique\. If a pathτ0∈A\\tau\_\{0\}\\in Ais duplicated,∇JERA\\nabla J\_\{\\mathrm\{ER\}\}^\{A\}acquires an additional termPθ\(τ0∣x\)∇logPθ\(τ0∣x\)P\_\{\\theta\}\(\\tau\_\{0\}\\mid x\)\\nabla\\log P\_\{\\theta\}\(\\tau\_\{0\}\\mid x\), every weight of∇JMLA\\nabla J\_\{\\mathrm\{ML\}\}^\{A\}changes, and∇JtropA\\nabla J\_\{\\mathrm\{trop\}\}^\{A\}is unchanged\.

###### Proof\.

For the first,∇eWθ​\(τ\)=eWθ​\(τ\)∇Wθ\(τ\)=Pθ\(τ∣x\)∇logPθ\(τ∣x\)\\nabla e^\{W\_\{\\theta\}\(\\tau\)\}=e^\{W\_\{\\theta\}\(\\tau\)\}\\nabla W\_\{\\theta\}\(\\tau\)=P\_\{\\theta\}\(\\tau\\mid x\)\\nabla\\log P\_\{\\theta\}\(\\tau\\mid x\); sum over the multiset\. For the second,∇log∑τeWθ​\(τ\)=\(∑τeWθ​\(τ\)∇Wθ\(τ\)\)/∑τ′eWθ​\(τ′\)\\nabla\\log\\sum\_\{\\tau\}e^\{W\_\{\\theta\}\(\\tau\)\}=\\big\(\\sum\_\{\\tau\}e^\{W\_\{\\theta\}\(\\tau\)\}\\nabla W\_\{\\theta\}\(\\tau\)\\big\)/\\sum\_\{\\tau^\{\\prime\}\}e^\{W\_\{\\theta\}\(\\tau^\{\\prime\}\)\}, which is the stated posterior weighting\. The third is Corollary[1](https://arxiv.org/html/2610.02478#Thmcorollary1)\(b\)\. Under duplication ofτ0\\tau\_\{0\}: the sum definingJERAJ\_\{\\mathrm\{ER\}\}^\{A\}gains a copy of the termeWθ​\(τ0\)e^\{W\_\{\\theta\}\(\\tau\_\{0\}\)\}and its gradient gains a copy of that term’s gradient; the denominator ofωML\\omega\_\{\\mathrm\{ML\}\}increases byPθ​\(τ0∣x\)P\_\{\\theta\}\(\\tau\_\{0\}\\mid x\)and the numerator of the weight onτ0\\tau\_\{0\}doubles, so all weights change; the multiset maximum and its unique maximizer are unchanged, hence so is the gradient ofJtropAJ\_\{\\mathrm\{trop\}\}^\{A\}\. ∎

The proposition gives the three objectives a common form and isolates their difference in the weight placed on each path\. The expected\-return weight is the path’s own probability, which is what makes on\-policy learning frequency weighted by construction\. The maximum\-likelihood weight is a posterior, which removes the dependence on absolute probability but still counts each retained realization\. The tropical weight is an indicator, and it is the only one of the three that Theorem[7](https://arxiv.org/html/2610.02478#Thmtheorem7)allows\. In TROPIC this is why the acquisition process may be arbitrarily off\-policy, why no importance weights appear, and why the coverage countermt​\(f\)m\_\{t\}\(f\)in Section[4\.3](https://arxiv.org/html/2610.02478#S4.SS3)counts rehearsals chosen by the algorithm rather than samples produced by the actor: the only frequency in the method is one the learner controls\.

### A\.4Compositional policy improvement

The classical policy improvement theorem says that acting greedily with respect to an exactQπQ^\{\\pi\}produces a policy at least as good asπ\\piat every state\. It requiresQπ​\(s,a\)Q^\{\\pi\}\(s,a\)for every action at every state visited, which for expected return means the total success mass of every subtree\. This section proves a tropical analogue with a different shape\. A single certified path is trained by maximum likelihood, exactly theK=1K=1update of Equation equation[14](https://arxiv.org/html/2610.02478#S4.E14), and the tropical value is shown to be non\-decreasing at*every*state of the retained graph, including states that were never trained from and never visited by the trained path\. Moreover the improvement is additive over shared fragments and reaches an interface undamped: a state whose best certified continuation merges into the trained path inherits the full gain accumulated on that path from the merge point on\.

Three properties of the maximum carry the proof, and it is worth naming them before the formalities\.*Substructure*: a best path that reaches a state on the trained path must continue along it, because suffixes of maximizers are maximizers\.*Join*: the value dominates the score of any particular path, so lower\-bounding the value only requires exhibiting one path whose score did not fall\.*Blindness*: the update can lower the log\-probabilities of non\-greedy actions at trained states, but no best path uses any of them, so the value never sees the loss\. The third is where the algebra bites; it is dominance \(R2 of Section[3](https://arxiv.org/html/2610.02478#S3)\) in dynamic form, and it is false for any aggregation that counts non\-maximal alternatives\.

Throughout this section the actor is tabular softmax withλ=1\\lambda=1, the boundary is binary, internal rewards are zero, and every nonterminal state on the trained path has at least two admissible actions \(a state with one action has nothing to learn\)\. Values are computed on the certified graph as described in Section[A\.1](https://arxiv.org/html/2610.02478#A1.SS1)\.

###### Definition 3\(Greedy action and greedy path\)\.

Fix a total order on the actions at every state\. Given logitszz, henceπ=πz\\pi=\\pi\_\{z\}, scoresw⁡\(s,a\)=log⁡π⁡\(a∣s\)w\(s,a\)=\\log\\pi\(a\\mid s\)and valuesQ⁡\(s,a\)=w⁡\(s,a\)\+V⁡\(T⁡\(s,a\)\)Q\(s,a\)=w\(s,a\)\+V\(T\(s,a\)\),V⁡\(s\)=maxa⁡Q⁡\(s,a\)V\(s\)=\\max\_\{a\}Q\(s,a\), the*greedy action*at a nonterminalsswithV⁡\(s\)\>−∞V\(s\)\>\-\\inftyis the first maximizera⋆​\(s\)=min⁡\{a∈𝒜⁡\(s\):Q⁡\(s,a\)=V⁡\(s\)\}a^\{\\star\}\(s\)=\\min\\\{a\\in\\mathcal\{A\}\(s\):Q\(s,a\)=V\(s\)\\\}, and the*greedy path*τ⋆​\(s\)\\tau^\{\\star\}\(s\)is defined recursively byτ⋆​\(s\)=\(s,a⋆​\(s\)\)∘τ⋆​\(T⁡\(s,a⋆​\(s\)\)\)\\tau^\{\\star\}\(s\)=\(s,a^\{\\star\}\(s\)\)\\circ\\tau^\{\\star\}\(T\(s,a^\{\\star\}\(s\)\)\), withτ⋆​\(y\)=y\\tau^\{\\star\}\(y\)=yat terminals\. The maps↦a⋆​\(s\)s\\mapsto a^\{\\star\}\(s\)is a deterministic policy on the graph andτ⋆​\(s\)\\tau^\{\\star\}\(s\)is its rollout fromss\.

###### Lemma 8\(The greedy path attains the value and has substructure\)\.

For every statesswithV⁡\(s\)\>−∞V\(s\)\>\-\\infty: the greedy pathτ⋆​\(s\)\\tau^\{\\star\}\(s\)ends at a terminalyywithRx​\(y\)=0R\_\{x\}\(y\)=0andW⁡\(τ⋆​\(s\)\)=V⁡\(s\)W\(\\tau^\{\\star\}\(s\)\)=V\(s\)\. For every stateu∈Sτ⋆​\(s\)u\\in S\_\{\\tau^\{\\star\}\(s\)\}the action taken there isa⋆​\(u\)a^\{\\star\}\(u\)and the suffix ofτ⋆​\(s\)\\tau^\{\\star\}\(s\)fromuuisτ⋆​\(u\)\\tau^\{\\star\}\(u\)\. In particular, if two greedy paths visit a common state they take the same action there and coincide from that state on\.

###### Proof\.

Induct in reverse topological order\. At a terminalV​\(y\)=Rx​\(y\)V\(y\)=R\_\{x\}\(y\), andV⁡\(y\)\>−∞V\(y\)\>\-\\inftyforcesRx​\(y\)=0=W⁡\(y\)R\_\{x\}\(y\)=0=W\(y\)\. At a nonterminalsswithV⁡\(s\)\>−∞V\(s\)\>\-\\infty, the maximumV⁡\(s\)=maxa⁡Q⁡\(s,a\)V\(s\)=\\max\_\{a\}Q\(s,a\)is attained bya⋆​\(s\)a^\{\\star\}\(s\), soV⁡\(T⁡\(s,a⋆​\(s\)\)\)\>−∞V\(T\(s,a^\{\\star\}\(s\)\)\)\>\-\\inftyand by inductionW⁡\(τ⋆​\(T⁡\(s,a⋆​\(s\)\)\)\)=V⁡\(T⁡\(s,a⋆​\(s\)\)\)W\(\\tau^\{\\star\}\(T\(s,a^\{\\star\}\(s\)\)\)\)=V\(T\(s,a^\{\\star\}\(s\)\)\)with an accepted terminal\. ThenW⁡\(τ⋆​\(s\)\)=w⁡\(s,a⋆​\(s\)\)\+W⁡\(τ⋆​\(T⁡\(s,a⋆​\(s\)\)\)\)=Q⁡\(s,a⋆​\(s\)\)=V⁡\(s\)W\(\\tau^\{\\star\}\(s\)\)=w\(s,a^\{\\star\}\(s\)\)\+W\(\\tau^\{\\star\}\(T\(s,a^\{\\star\}\(s\)\)\)\)=Q\(s,a^\{\\star\}\(s\)\)=V\(s\)\. The substructure statements are immediate from the recursive definition: at each state visited, the path takesa⋆a^\{\\star\}of that state and continues with the greedy path of the successor, so the suffix from any visiteduuis by constructionτ⋆​\(u\)\\tau^\{\\star\}\(u\), which depends onuualone\. ∎

###### Definition 4\(Tropical greedy update\)\.

Letτ=τ⋆​\(s0\)\\tau=\\tau^\{\\star\}\(s\_\{0\}\)with nonterminal state setSτS\_\{\\tau\}, and letη\>0\\eta\>0\. The tropical greedy update is one gradient step on the log\-likelihood ofτ\\tauwith respect to the logits,

z′=z\+η​∇z​∑\(s,a\)∈τlog⁡πz​\(a∣s\)\.z^\{\\prime\}=z\+\\eta\\,\\nabla\_\{z\}\\sum\_\{\(s,a\)\\in\\tau\}\\log\\pi\_\{z\}\(a\\mid s\)\.Because a path visits each state once and logits at different states are independent, this readszs,⋅′=zs,⋅z^\{\\prime\}\_\{s,\\cdot\}=z\_\{s,\\cdot\}fors∉Sτs\\notin S\_\{\\tau\}and

zs,a′=zs,a\+η\(𝟏\{a=a⋆\(s\)\}−π\(a∣s\)\)fors∈Sτ,a∈𝒜\(s\)\.z^\{\\prime\}\_\{s,a\}=z\_\{s,a\}\+\\eta\\big\(\\mathbf\{1\}\\\{a=a^\{\\star\}\(s\)\\\}\-\\pi\(a\\mid s\)\\big\)\\qquad\\text\{for \}s\\in S\_\{\\tau\},\\ a\\in\\mathcal\{A\}\(s\)\.It is theK=1K=1update of Equation equation[14](https://arxiv.org/html/2610.02478#S4.E14)for one problem, without the token normalization\. Primes denote quantities underz′z^\{\\prime\}, andΔ​w​\(s,a\)=w′​\(s,a\)−w⁡\(s,a\)\\Delta w\(s,a\)=w^\{\\prime\}\(s,a\)\-w\(s,a\)\.

###### Lemma 9\(Local effect of the update\)\.

1. \(a\)Δ​w​\(s,a\)=0\\Delta w\(s,a\)=0for everys∉Sτs\\notin S\_\{\\tau\}and everyaa\.
2. \(b\)Fors∈Sτs\\in S\_\{\\tau\}anda≠a⋆​\(s\)a\\neq a^\{\\star\}\(s\),Δ​w​\(s,a⋆​\(s\)\)−Δ​w​\(s,a\)=η⁡\(1−π⁡\(a⋆​\(s\)∣s\)\+π⁡\(a∣s\)\)\>0\\Delta w\(s,a^\{\\star\}\(s\)\)\-\\Delta w\(s,a\)=\\eta\\big\(1\-\\pi\(a^\{\\star\}\(s\)\\mid s\)\+\\pi\(a\\mid s\)\\big\)\>0\.
3. \(c\)Fors∈Sτs\\in S\_\{\\tau\},Δ​w​\(s,a⋆​\(s\)\)\>0\\Delta w\(s,a^\{\\star\}\(s\)\)\>0\.
4. \(d\)ConsequentlyΔ​w​\(s,a\)≤Δ​w​\(s,a⋆​\(s\)\)\\Delta w\(s,a\)\\leq\\Delta w\(s,a^\{\\star\}\(s\)\)for alls∈Sτs\\in S\_\{\\tau\}and allaa, withΔ​w​\(s,a⋆​\(s\)\)≥0\\Delta w\(s,a^\{\\star\}\(s\)\)\\geq 0for allsson or offτ\\tau\.

###### Proof\.

\(a\) The logits atssare unchanged, hence so isπ\(⋅∣s\)\\pi\(\\cdot\\mid s\)\. \(b\) At any state,w\(s,a\)=zs,a−log∑a′ezs,a′w\(s,a\)=z\_\{s,a\}\-\\log\\sum\_\{a^\{\\prime\}\}e^\{z\_\{s,a^\{\\prime\}\}\}, soΔw\(s,a\)=Δzs,a−\[log∑a′ezs,a′′−log∑a′ezs,a′\]\\Delta w\(s,a\)=\\Delta z\_\{s,a\}\-\\big\[\\log\\sum\_\{a^\{\\prime\}\}e^\{z^\{\\prime\}\_\{s,a^\{\\prime\}\}\}\-\\log\\sum\_\{a^\{\\prime\}\}e^\{z\_\{s,a^\{\\prime\}\}\}\\big\], and the bracket does not depend onaa\. Subtracting the expressions fora⋆​\(s\)a^\{\\star\}\(s\)andaa,Δ​w​\(s,a⋆​\(s\)\)−Δ​w​\(s,a\)=Δ​zs,a⋆​\(s\)−Δ​zs,a=η⁡\(1−π⁡\(a⋆​\(s\)∣s\)\)\+η​π​\(a∣s\)\\Delta w\(s,a^\{\\star\}\(s\)\)\-\\Delta w\(s,a\)=\\Delta z\_\{s,a^\{\\star\}\(s\)\}\-\\Delta z\_\{s,a\}=\\eta\(1\-\\pi\(a^\{\\star\}\(s\)\\mid s\)\)\+\\eta\\pi\(a\\mid s\), which is positive sinceπ⁡\(a⋆​\(s\)∣s\)<1\\pi\(a^\{\\star\}\(s\)\\mid s\)<1whensshas at least two actions\. \(c\) Writeπ⁡\(a⋆∣s\)=\(1\+∑a≠a⋆ezs,a−zs,a⋆\)−1\\pi\(a^\{\\star\}\\mid s\)=\\big\(1\+\\sum\_\{a\\neq a^\{\\star\}\}e^\{z\_\{s,a\}\-z\_\{s,a^\{\\star\}\}\}\\big\)^\{\-1\}and likewise forz′z^\{\\prime\}\. By \(b\) each exponentzs,a′−zs,a⋆′z^\{\\prime\}\_\{s,a\}\-z^\{\\prime\}\_\{s,a^\{\\star\}\}is strictly smaller thanzs,a−zs,a⋆z\_\{s,a\}\-z\_\{s,a^\{\\star\}\}, so the sum strictly decreases andπ′​\(a⋆∣s\)\>π⁡\(a⋆∣s\)\\pi^\{\\prime\}\(a^\{\\star\}\\mid s\)\>\\pi\(a^\{\\star\}\\mid s\), i\.e\.Δ​w​\(s,a⋆​\(s\)\)\>0\\Delta w\(s,a^\{\\star\}\(s\)\)\>0\. \(d\) is \(b\), \(c\) and \(a\) together\. ∎

Part \(b\) is the exact statement of blindness: whatever normalization does to the probabilities of the other actions at a trained state, the greedy action gains strictly more than any of them, in log units, by an amount that does not depend on the value function at all\. Part \(c\) says the greedy action’s own log\-probability rises\. Nothing is claimed about the other actions individually; with three or more actions some of them may gain probability from the dominant one\. The proofs below never need them to lose\.

###### Lemma 10\(Gain bound\)\.

For every pathτ′\\tau^\{\\prime\}in the certified graph,

W′​\(τ′\)−W⁡\(τ′\)≤∑x∈Sτ′∩SτΔ​w​\(x,a⋆​\(x\)\),W^\{\\prime\}\(\\tau^\{\\prime\}\)\-W\(\\tau^\{\\prime\}\)\\ \\leq\\ \\sum\_\{x\\in S\_\{\\tau^\{\\prime\}\}\\cap S\_\{\\tau\}\}\\Delta w\(x,a^\{\\star\}\(x\)\),and for every statevv,

V′​\(v\)≤V⁡\(v\)\+∑x∈Sτ∩Desc⁡\(v\)Δ​w​\(x,a⋆​\(x\)\)\.V^\{\\prime\}\(v\)\\ \\leq\\ V\(v\)\+\\sum\_\{x\\in S\_\{\\tau\}\\cap\\operatorname\{Desc\}\(v\)\}\\Delta w\(x,a^\{\\star\}\(x\)\)\.

###### Proof\.

W′​\(τ′\)−W⁡\(τ′\)=∑\(x,a\)∈τ′Δ​w​\(x,a\)W^\{\\prime\}\(\\tau^\{\\prime\}\)\-W\(\\tau^\{\\prime\}\)=\\sum\_\{\(x,a\)\\in\\tau^\{\\prime\}\}\\Delta w\(x,a\)\. Forx∉Sτx\\notin S\_\{\\tau\}the term is00by Lemma[9](https://arxiv.org/html/2610.02478#Thmtheorem9)\(a\); forx∈Sτx\\in S\_\{\\tau\}it is at mostΔ​w​\(x,a⋆​\(x\)\)\\Delta w\(x,a^\{\\star\}\(x\)\)by Lemma[9](https://arxiv.org/html/2610.02478#Thmtheorem9)\(d\)\. This gives the first inequality\. For the second, ifV⁡\(v\)=−∞V\(v\)=\-\\inftythen no certified path leavesvvandV′​\(v\)=−∞V^\{\\prime\}\(v\)=\-\\inftyas well, since the graph and the boundary are unchanged\. Otherwise every pathτ′\\tau^\{\\prime\}fromvvhasSτ′⊆Desc⁡\(v\)S\_\{\\tau^\{\\prime\}\}\\subseteq\\operatorname\{Desc\}\(v\), and since eachΔ​w​\(x,a⋆​\(x\)\)≥0\\Delta w\(x,a^\{\\star\}\(x\)\)\\geq 0,

V′​\(v\)=maxτ′⁡W′​\(τ′\)≤maxτ′⁡\[W⁡\(τ′\)\+∑x∈Sτ∩Desc⁡\(v\)Δ​w​\(x,a⋆​\(x\)\)\]=V⁡\(v\)\+∑x∈Sτ∩Desc⁡\(v\)Δ​w​\(x,a⋆​\(x\)\)\.V^\{\\prime\}\(v\)=\\max\_\{\\tau^\{\\prime\}\}W^\{\\prime\}\(\\tau^\{\\prime\}\)\\leq\\max\_\{\\tau^\{\\prime\}\}\\Big\[W\(\\tau^\{\\prime\}\)\+\\sum\_\{x\\in S\_\{\\tau\}\\cap\\operatorname\{Desc\}\(v\)\}\\Delta w\(x,a^\{\\star\}\(x\)\)\\Big\]=V\(v\)\+\\sum\_\{x\\in S\_\{\\tau\}\\cap\\operatorname\{Desc\}\(v\)\}\\Delta w\(x,a^\{\\star\}\(x\)\)\.∎

###### Lemma 11\(Stability along the trained path, with exact gain\)\.

Writeτ=\(\(u0,a0\),…,\(um−1,am−1\),um\)\\tau=\\big\(\(u\_\{0\},a\_\{0\}\),\\dots,\(u\_\{m\-1\},a\_\{m\-1\}\),u\_\{m\}\\big\)withu0=s0u\_\{0\}=s\_\{0\},ak=a⋆​\(uk\)a\_\{k\}=a^\{\\star\}\(u\_\{k\}\)andumu\_\{m\}an accepted terminal, and setΔ≥k=∑j=km−1Δ​w​\(uj,aj\)\\Delta\_\{\\geq k\}=\\sum\_\{j=k\}^\{m\-1\}\\Delta w\(u\_\{j\},a\_\{j\}\)for0≤k≤m0\\leq k\\leq m, soΔ≥m=0\\Delta\_\{\\geq m\}=0\. Then for everykk:

V′​\(uk\)=V⁡\(uk\)\+Δ≥k,V^\{\\prime\}\(u\_\{k\}\)=V\(u\_\{k\}\)\+\\Delta\_\{\\geq k\},and fork<mk<mthe actionaka\_\{k\}is the unique maximizer ofQ′​\(uk,⋅\)Q^\{\\prime\}\(u\_\{k\},\\cdot\)\. In particular the greedy policy is unchanged onSτS\_\{\\tau\}, the greedy path froms0s\_\{0\}underz′z^\{\\prime\}is againτ\\tau, andΔ≥k\>0\\Delta\_\{\\geq k\}\>0fork<mk<m\.

###### Proof\.

Backward induction onkk\. Fork=mk=m,V′​\(um\)=Rx​\(um\)=0=V⁡\(um\)V^\{\\prime\}\(u\_\{m\}\)=R\_\{x\}\(u\_\{m\}\)=0=V\(u\_\{m\}\)andΔ≥m=0\\Delta\_\{\\geq m\}=0\. Assume the claim fork\+1k\+1and consideruku\_\{k\}\.

For the greedy action, sinceaka\_\{k\}attainsV⁡\(uk\)V\(u\_\{k\}\)we haveV⁡\(uk\)=w⁡\(uk,ak\)\+V⁡\(uk\+1\)V\(u\_\{k\}\)=w\(u\_\{k\},a\_\{k\}\)\+V\(u\_\{k\+1\}\), and therefore

Q′​\(uk,ak\)=w′​\(uk,ak\)\+V′​\(uk\+1\)=w⁡\(uk,ak\)\+Δ​w​\(uk,ak\)\+V⁡\(uk\+1\)\+Δ≥k\+1=V⁡\(uk\)\+Δ≥k\.Q^\{\\prime\}\(u\_\{k\},a\_\{k\}\)=w^\{\\prime\}\(u\_\{k\},a\_\{k\}\)\+V^\{\\prime\}\(u\_\{k\+1\}\)=w\(u\_\{k\},a\_\{k\}\)\+\\Delta w\(u\_\{k\},a\_\{k\}\)\+V\(u\_\{k\+1\}\)\+\\Delta\_\{\\geq k\+1\}=V\(u\_\{k\}\)\+\\Delta\_\{\\geq k\}\.
For any other actiona≠aka\\neq a\_\{k\}, letv=T⁡\(uk,a\)v=T\(u\_\{k\},a\)\. The statesu0,…,uku\_\{0\},\\dots,u\_\{k\}are ancestors ofvv:uku\_\{k\}is a parent ofvv, and eachuju\_\{j\}withj<kj<kis an ancestor ofuku\_\{k\}\. By acyclicity none of them lies inDesc⁡\(v\)\\operatorname\{Desc\}\(v\), soSτ∩Desc⁡\(v\)⊆\{uk\+1,…,um−1\}S\_\{\\tau\}\\cap\\operatorname\{Desc\}\(v\)\\subseteq\\\{u\_\{k\+1\},\\dots,u\_\{m\-1\}\\\}and Lemma[10](https://arxiv.org/html/2610.02478#Thmtheorem10)givesV′​\(v\)≤V⁡\(v\)\+Δ≥k\+1V^\{\\prime\}\(v\)\\leq V\(v\)\+\\Delta\_\{\\geq k\+1\}\. Hence, usingQ⁡\(uk,a\)=w⁡\(uk,a\)\+V⁡\(v\)≤V⁡\(uk\)Q\(u\_\{k\},a\)=w\(u\_\{k\},a\)\+V\(v\)\\leq V\(u\_\{k\}\),

Q′​\(uk,a\)=w′​\(uk,a\)\+V′​\(v\)≤w⁡\(uk,a\)\+Δ​w​\(uk,a\)\+V⁡\(v\)\+Δ≥k\+1≤V⁡\(uk\)\+Δ​w​\(uk,a\)\+Δ≥k\+1\.Q^\{\\prime\}\(u\_\{k\},a\)=w^\{\\prime\}\(u\_\{k\},a\)\+V^\{\\prime\}\(v\)\\leq w\(u\_\{k\},a\)\+\\Delta w\(u\_\{k\},a\)\+V\(v\)\+\\Delta\_\{\\geq k\+1\}\\leq V\(u\_\{k\}\)\+\\Delta w\(u\_\{k\},a\)\+\\Delta\_\{\\geq k\+1\}\.Subtracting,

Q′​\(uk,ak\)−Q′​\(uk,a\)≥Δ​w​\(uk,ak\)−Δ​w​\(uk,a\)=η⁡\(1−π⁡\(ak∣uk\)\+π⁡\(a∣uk\)\)\>0Q^\{\\prime\}\(u\_\{k\},a\_\{k\}\)\-Q^\{\\prime\}\(u\_\{k\},a\)\\ \\geq\\ \\Delta w\(u\_\{k\},a\_\{k\}\)\-\\Delta w\(u\_\{k\},a\)=\\eta\\big\(1\-\\pi\(a\_\{k\}\\mid u\_\{k\}\)\+\\pi\(a\\mid u\_\{k\}\)\\big\)\>0by Lemma[9](https://arxiv.org/html/2610.02478#Thmtheorem9)\(b\)\. \(IfV⁡\(v\)=−∞V\(v\)=\-\\inftythe inequality is trivial\.\) Soaka\_\{k\}is the unique maximizer ofQ′​\(uk,⋅\)Q^\{\\prime\}\(u\_\{k\},\\cdot\)andV′​\(uk\)=Q′​\(uk,ak\)=V⁡\(uk\)\+Δ≥kV^\{\\prime\}\(u\_\{k\}\)=Q^\{\\prime\}\(u\_\{k\},a\_\{k\}\)=V\(u\_\{k\}\)\+\\Delta\_\{\\geq k\}\. Since the first maximizer is the unique maximizer,a′⁣⋆​\(uk\)=aka^\{\\prime\\star\}\(u\_\{k\}\)=a\_\{k\}; applying this alongτ\\taushows the greedy path froms0s\_\{0\}is unchanged\. FinallyΔ≥k\>0\\Delta\_\{\\geq k\}\>0fork<mk<mbecause each summand is positive by Lemma[9](https://arxiv.org/html/2610.02478#Thmtheorem9)\(c\)\. ∎

###### Theorem 12\(Compositional policy improvement\)\.

Letτ=τ⋆​\(s0\)\\tau=\\tau^\{\\star\}\(s\_\{0\}\)and letz′z^\{\\prime\}be the tropical greedy update alongτ\\tauwith any stepη\>0\\eta\>0\.

1. \(i\)\(Pointwise improvement from one path\.\)For every statessof the certified graph,V′​\(s\)≥V⁡\(s\)V^\{\\prime\}\(s\)\\geq V\(s\)\.
2. \(ii\)\(Additivity over shared fragments\.\)For everysswithV⁡\(s\)\>−∞V\(s\)\>\-\\infty, V′​\(s\)−V⁡\(s\)≥∑x∈Sτ⋆​\(s\)∩SτΔ​w​\(x,a⋆​\(x\)\)\.V^\{\\prime\}\(s\)\-V\(s\)\\ \\geq\\ \\sum\_\{x\\in S\_\{\\tau^\{\\star\}\(s\)\}\\cap S\_\{\\tau\}\}\\Delta w\(x,a^\{\\star\}\(x\)\)\.
3. \(iii\)\(Undamped propagation to interfaces\.\)Ifτ⋆​\(s\)\\tau^\{\\star\}\(s\)visits a state ofτ\\tauanduku\_\{k\}is the first such state, thenτ⋆​\(s\)\\tau^\{\\star\}\(s\)coincides withτ\\taufromuku\_\{k\}on and V′​\(s\)−V⁡\(s\)≥V′​\(uk\)−V⁡\(uk\)=Δ≥k\>0\.V^\{\\prime\}\(s\)\-V\(s\)\\ \\geq\\ V^\{\\prime\}\(u\_\{k\}\)\-V\(u\_\{k\}\)=\\Delta\_\{\\geq k\}\>0\.
4. \(iv\)\(Iteration\.\)Repeating the update produces, at every state, a non\-decreasing sequence of values, with the same trained path at every step\.

###### Proof\.

\(i\)–\(ii\)\. IfV⁡\(s\)=−∞V\(s\)=\-\\inftythenV′​\(s\)=−∞V^\{\\prime\}\(s\)=\-\\inftyand \(i\) holds with equality\. Otherwise letτ⋆​\(s\)\\tau^\{\\star\}\(s\)be the greedy path fromssunderzz; by Lemma[8](https://arxiv.org/html/2610.02478#Thmtheorem8)it is certified andW⁡\(τ⋆​\(s\)\)=V⁡\(s\)W\(\\tau^\{\\star\}\(s\)\)=V\(s\)\. By the join propertyV′​\(s\)≥W′​\(τ⋆​\(s\)\)V^\{\\prime\}\(s\)\\geq W^\{\\prime\}\(\\tau^\{\\star\}\(s\)\), andW′​\(τ⋆​\(s\)\)−W⁡\(τ⋆​\(s\)\)=∑\(x,a\)∈τ⋆​\(s\)Δ​w​\(x,a\)W^\{\\prime\}\(\\tau^\{\\star\}\(s\)\)\-W\(\\tau^\{\\star\}\(s\)\)=\\sum\_\{\(x,a\)\\in\\tau^\{\\star\}\(s\)\}\\Delta w\(x,a\)\. Forx∉Sτx\\notin S\_\{\\tau\}the term is00\(Lemma[9](https://arxiv.org/html/2610.02478#Thmtheorem9)\(a\)\)\. Forx∈Sτx\\in S\_\{\\tau\}, Lemma[8](https://arxiv.org/html/2610.02478#Thmtheorem8)says the action taken byτ⋆​\(s\)\\tau^\{\\star\}\(s\)atxxisa⋆​\(x\)a^\{\\star\}\(x\), so the term isΔ​w​\(x,a⋆​\(x\)\)\>0\\Delta w\(x,a^\{\\star\}\(x\)\)\>0\(Lemma[9](https://arxiv.org/html/2610.02478#Thmtheorem9)\(c\)\)\. HenceV′​\(s\)≥V⁡\(s\)\+∑x∈Sτ⋆​\(s\)∩SτΔ​w​\(x,a⋆​\(x\)\)≥V⁡\(s\)V^\{\\prime\}\(s\)\\geq V\(s\)\+\\sum\_\{x\\in S\_\{\\tau^\{\\star\}\(s\)\}\\cap S\_\{\\tau\}\}\\Delta w\(x,a^\{\\star\}\(x\)\)\\geq V\(s\), which is \(ii\) and \(i\)\.

\(iii\)\. The states ofτ⋆​\(s\)\\tau^\{\\star\}\(s\)beforeuku\_\{k\}lie outsideSτS\_\{\\tau\}, by the choice ofuku\_\{k\}\. Fromuku\_\{k\}on,τ⋆​\(s\)\\tau^\{\\star\}\(s\)equalsτ⋆​\(uk\)\\tau^\{\\star\}\(u\_\{k\}\)by Lemma[8](https://arxiv.org/html/2610.02478#Thmtheorem8), and so does the suffix ofτ\\taufromuku\_\{k\}, sinceτ=τ⋆​\(s0\)\\tau=\\tau^\{\\star\}\(s\_\{0\}\)visitsuku\_\{k\}\. ThereforeSτ⋆​\(s\)∩Sτ=\{uk,…,um−1\}S\_\{\\tau^\{\\star\}\(s\)\}\\cap S\_\{\\tau\}=\\\{u\_\{k\},\\dots,u\_\{m\-1\}\\\}and the sum in \(ii\) equalsΔ≥k\\Delta\_\{\\geq k\}, which isV′​\(uk\)−V⁡\(uk\)V^\{\\prime\}\(u\_\{k\}\)\-V\(u\_\{k\}\)by Lemma[11](https://arxiv.org/html/2610.02478#Thmtheorem11)and is positive\.

\(iv\)\. By Lemma[11](https://arxiv.org/html/2610.02478#Thmtheorem11)the greedy path froms0s\_\{0\}underz′z^\{\\prime\}is againτ\\tau, so the next update is a tropical greedy update along the same path and \(i\) applies again\. ∎

Read \(iii\) as a statement about composition\. The statesswas never trained from and the pathτ⋆​\(s\)\\tau^\{\\star\}\(s\)was never sampled; it is a prefix fromsstouku\_\{k\}, discovered in some rollout, composed at the interfaceuku\_\{k\}with a suffix that was trained as part of a different path\. The theorem says that all of the training on that suffix is inherited byss, in full, in log units\. Under expected return the change atssfrom training atuku\_\{k\}is scaled by the share ofss’s success mass that flows throughuku\_\{k\}, and is further reduced by the mass lost on suppressed alternatives; under the maximum neither attenuation exists, because the value atssis the score of one path and that path does not use any suppressed alternative\.

The next proposition establishes that the improvement step of Theorem[12](https://arxiv.org/html/2610.02478#Thmtheorem12)is genuinely a different step from classical policy improvement, in two senses: the action it reinforces cannot be determined from expected\-return information, and acting on expected\-return information can destroy the tropical value while the tropical step can destroy expected return\. The example is the one from Proposition, lifted from values to decisions\.

###### Proposition 4\(Incompatibility with expected\-return improvement\)\.

1. \(a\)\(Non\-identifiability\.\)There exist two instances that agree on a stateuu, onπ\(⋅∣u\)\\pi\(\\cdot\\mid u\), onVπ¯​\(T​\(u,a\)\)V^\{\\bar\{\\pi\}\}\(T\(u,a\)\)for every action, and onVπ¯​\(u\)V^\{\\bar\{\\pi\}\}\(u\), yet have different tropical greedy actions atuu\. Hence no rule that selects an action from these quantities selects the tropical greedy action on all instances\.
2. \(b\)\(Mutual harm\.\)Letuuhave two actionsa,a′a,a^\{\\prime\}withaathe unique tropical greedy action anda′a^\{\\prime\}the unique expected\-return greedy action,Vπ¯​\(T⁡\(u,a′\)\)\>Vπ¯​\(T⁡\(u,a\)\)V^\{\\bar\{\\pi\}\}\(T\(u,a^\{\\prime\}\)\)\>V^\{\\bar\{\\pi\}\}\(T\(u,a\)\)\. Any update that increasesπ⁡\(a∣u\)\\pi\(a\\mid u\)and changes no other state strictly decreasesVπ¯​\(u\)V^\{\\bar\{\\pi\}\}\(u\)\. Any update that increasesπ⁡\(a′∣u\)\\pi\(a^\{\\prime\}\\mid u\)and changes no other state strictly decreasesVtropπ¯​\(u\)V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(u\)providedlog⁡π′​\(a′∣u\)π⁡\(a′∣u\)<−Atropπ¯​\(u,a′\)\\log\\frac\{\\pi^\{\\prime\}\(a^\{\\prime\}\\mid u\)\}\{\\pi\(a^\{\\prime\}\\mid u\)\}<\-A^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(u,a^\{\\prime\}\), in particular for all sufficiently small steps\.

###### Proof\.

\(a\) Takeπ⁡\(a∣u\)=π⁡\(a′∣u\)=12\\pi\(a\\mid u\)=\\pi\(a^\{\\prime\}\\mid u\)=\\tfrac\{1\}\{2\}in both instances\. In the first,T⁡\(u,a\)T\(u,a\)has a single certified continuation of probability12\\tfrac\{1\}\{2\}andT⁡\(u,a′\)T\(u,a^\{\\prime\}\)has three of probability14\\tfrac\{1\}\{4\}each\. In the second,T⁡\(u,a\)T\(u,a\)has two of probability14\\tfrac\{1\}\{4\}andT⁡\(u,a′\)T\(u,a^\{\\prime\}\)one of probability34\\tfrac\{3\}\{4\}\. In both,Vπ¯​\(T⁡\(u,a\)\)=12V^\{\\bar\{\\pi\}\}\(T\(u,a\)\)=\\tfrac\{1\}\{2\},Vπ¯​\(T⁡\(u,a′\)\)=34V^\{\\bar\{\\pi\}\}\(T\(u,a^\{\\prime\}\)\)=\\tfrac\{3\}\{4\}andVπ¯​\(u\)=12⋅12\+12⋅34=58V^\{\\bar\{\\pi\}\}\(u\)=\\tfrac\{1\}\{2\}\\cdot\\tfrac\{1\}\{2\}\+\\tfrac\{1\}\{2\}\\cdot\\tfrac\{3\}\{4\}=\\tfrac\{5\}\{8\}\. The tropicalQQ\-values arelog⁡π⁡\(a∣u\)\+max⁡log⁡P\\log\\pi\(a\\mid u\)\+\\max\\log Pover the subtree: in the first instancelog⁡\(12⋅12\)=log⁡14\\log\(\\tfrac\{1\}\{2\}\\cdot\\tfrac\{1\}\{2\}\)=\\log\\tfrac\{1\}\{4\}foraaagainstlog⁡\(12⋅14\)=log⁡18\\log\(\\tfrac\{1\}\{2\}\\cdot\\tfrac\{1\}\{4\}\)=\\log\\tfrac\{1\}\{8\}fora′a^\{\\prime\}, so the tropical greedy action isaa; in the second,log⁡18\\log\\tfrac\{1\}\{8\}foraaagainstlog⁡\(12⋅34\)=log⁡38\\log\(\\tfrac\{1\}\{2\}\\cdot\\tfrac\{3\}\{4\}\)=\\log\\tfrac\{3\}\{8\}fora′a^\{\\prime\}, so it isa′a^\{\\prime\}\. A rule that is a function of the listed quantities returns the same action in both instances and is therefore wrong in one of them\.

\(b\) With two actions,π⁡\(a′∣u\)=1−π⁡\(a∣u\)\\pi\(a^\{\\prime\}\\mid u\)=1\-\\pi\(a\\mid u\)and downstream values are unchanged by an update atuu, so

Vπ¯​\(u\)=π⁡\(a∣u\)​Vπ¯​\(T⁡\(u,a\)\)\+\(1−π⁡\(a∣u\)\)​Vπ¯​\(T⁡\(u,a′\)\)V^\{\\bar\{\\pi\}\}\(u\)=\\pi\(a\\mid u\)V^\{\\bar\{\\pi\}\}\(T\(u,a\)\)\+\\big\(1\-\\pi\(a\\mid u\)\\big\)V^\{\\bar\{\\pi\}\}\(T\(u,a^\{\\prime\}\)\)=Vπ¯​\(T⁡\(u,a′\)\)−π⁡\(a∣u\)​\[Vπ¯​\(T⁡\(u,a′\)\)−Vπ¯​\(T⁡\(u,a\)\)\]\.=V^\{\\bar\{\\pi\}\}\(T\(u,a^\{\\prime\}\)\)\-\\pi\(a\\mid u\)\\big\[V^\{\\bar\{\\pi\}\}\(T\(u,a^\{\\prime\}\)\)\-V^\{\\bar\{\\pi\}\}\(T\(u,a\)\)\\big\]\.The bracket is positive by hypothesis, so increasingπ⁡\(a∣u\)\\pi\(a\\mid u\)strictly decreasesVπ¯​\(u\)V^\{\\bar\{\\pi\}\}\(u\)\.

For the second claim writeA=w⁡\(u,a\)\+Vtropπ¯​\(T⁡\(u,a\)\)A=w\(u,a\)\+V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(T\(u,a\)\)andB=w⁡\(u,a′\)\+Vtropπ¯​\(T⁡\(u,a′\)\)B=w\(u,a^\{\\prime\}\)\+V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(T\(u,a^\{\\prime\}\)\), soVtropπ¯​\(u\)=max⁡\{A,B\}=A\>BV^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(u\)=\\max\\\{A,B\\\}=A\>BandAtropπ¯​\(u,a′\)=B−A<0A^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(u,a^\{\\prime\}\)=B\-A<0\. An update increasingπ⁡\(a′∣u\)\\pi\(a^\{\\prime\}\\mid u\)decreasesπ⁡\(a∣u\)\\pi\(a\\mid u\), sow′​\(u,a\)<w⁡\(u,a\)w^\{\\prime\}\(u,a\)<w\(u,a\)andA′<AA^\{\\prime\}<A, whileB′=B\+log⁡π′​\(a′∣u\)π⁡\(a′∣u\)B^\{\\prime\}=B\+\\log\\frac\{\\pi^\{\\prime\}\(a^\{\\prime\}\\mid u\)\}\{\\pi\(a^\{\\prime\}\\mid u\)\}\. ThenVtropπ¯​\(u\)′=max⁡\{A′,B′\}<A=Vtropπ¯​\(u\)V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(u\)^\{\\prime\}=\\max\\\{A^\{\\prime\},B^\{\\prime\}\\\}<A=V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(u\)as soon asB′<AB^\{\\prime\}<A, i\.e\. as soon aslog⁡π′​\(a′∣u\)π⁡\(a′∣u\)<A−B=−Atropπ¯​\(u,a′\)\\log\\frac\{\\pi^\{\\prime\}\(a^\{\\prime\}\\mid u\)\}\{\\pi\(a^\{\\prime\}\\mid u\)\}<A\-B=\-A^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(u,a^\{\\prime\}\)\. Since the left side tends to00with the step size and the right side is a fixed positive number, the condition holds for all sufficiently small steps\. ∎

### A\.5The tropical performance difference lemma

The performance difference lemma expresses the change in value between two policies as an expectation, under the new policy’s trajectory distribution, of the old policy’s advantage\. Everything that is hard in classical policy optimization lives in that expectation: it is over a distribution one does not have, its gradient carries the visitation weightdπ​\(s\)​π​\(a∣s\)d^\{\\pi\}\(s\)\\pi\(a\\mid s\)that makes rare good paths invisible, and convergence rates inherit a distribution mismatch coefficient from it\. This section derives the tropical analogue and shows that the expectation is replaced by a sum over a single path\. In this sectionλ\>0\\lambda\>0and the internal rewardrrare general and terminal scoresg⁡\(y\)g\(y\)may be graded; the binary boundary is the caseg=Rxg=R\_\{x\}\.

###### Lemma 13\(Path form and path identity\)\.

For an actorπ\\piletQπ,Vπ,AπQ^\{\\pi\},V^\{\\pi\},A^\{\\pi\}be given by Equation equation[6](https://arxiv.org/html/2610.02478#S4.E6)withVπ​\(y\)=g​\(y\)V^\{\\pi\}\(y\)=g\(y\)at terminals, and letWπ​\(τ\)=∑t\[λ​log⁡π⁡\(at∣st\)\+r⁡\(st,at\)\]\+g⁡\(y\)W\_\{\\pi\}\(\\tau\)=\\sum\_\{t\}\\big\[\\lambda\\log\\pi\(a\_\{t\}\\mid s\_\{t\}\)\+r\(s\_\{t\},a\_\{t\}\)\\big\]\+g\(y\)\.

1. \(a\)Vπ​\(s\)=maxτ​from​s⁡Wπ​\(τ\)V^\{\\pi\}\(s\)=\\max\_\{\\tau\\text\{ from \}s\}W\_\{\\pi\}\(\\tau\)for everyss\.
2. \(b\)For every pathτ′\\tau^\{\\prime\}fromssto a terminalyywithg⁡\(y\)\>−∞g\(y\)\>\-\\infty, Wπ​\(τ′\)=Vπ​\(s\)\+∑\(st,at\)∈τ′Aπ​\(st,at\)\.W\_\{\\pi\}\(\\tau^\{\\prime\}\)=V^\{\\pi\}\(s\)\+\\sum\_\{\(s\_\{t\},a\_\{t\}\)\\in\\tau^\{\\prime\}\}A^\{\\pi\}\(s\_\{t\},a\_\{t\}\)\.

###### Proof\.

\(a\) Reverse topological induction\. At terminals both sides equalg⁡\(y\)g\(y\)\. At a nonterminalss, every path fromssis\(s,a\)\(s,a\)followed by a path fromT⁡\(s,a\)T\(s,a\), and additivity givesmaxτ⁡Wπ​\(τ\)=maxa⁡\[λ​log⁡π⁡\(a∣s\)\+r⁡\(s,a\)\+maxτ′′​from​T​\(s,a\)⁡Wπ​\(τ′′\)\]=maxa⁡Qπ​\(s,a\)=Vπ​\(s\)\\max\_\{\\tau\}W\_\{\\pi\}\(\\tau\)=\\max\_\{a\}\\big\[\\lambda\\log\\pi\(a\\mid s\)\+r\(s,a\)\+\\max\_\{\\tau^\{\\prime\\prime\}\\text\{ from \}T\(s,a\)\}W\_\{\\pi\}\(\\tau^\{\\prime\\prime\}\)\\big\]=\\max\_\{a\}Q^\{\\pi\}\(s,a\)=V^\{\\pi\}\(s\)by the induction hypothesis\.

\(b\) Alongτ′\\tau^\{\\prime\}every valueVπ​\(st\)V^\{\\pi\}\(s\_\{t\}\)is finite, since the suffix ofτ′\\tau^\{\\prime\}fromsts\_\{t\}is a path with finite score and \(a\) givesVπ​\(st\)≥V^\{\\pi\}\(s\_\{t\}\)\\geqthat score\. Then, withsH=ys\_\{H\}=y,

∑t=0H−1Aπ​\(st,at\)=∑t=0H−1\[λ​log⁡π⁡\(at∣st\)\+r⁡\(st,at\)\+Vπ​\(st\+1\)−Vπ​\(st\)\]\\sum\_\{t=0\}^\{H\-1\}A^\{\\pi\}\(s\_\{t\},a\_\{t\}\)=\\sum\_\{t=0\}^\{H\-1\}\\big\[\\lambda\\log\\pi\(a\_\{t\}\\mid s\_\{t\}\)\+r\(s\_\{t\},a\_\{t\}\)\+V^\{\\pi\}\(s\_\{t\+1\}\)\-V^\{\\pi\}\(s\_\{t\}\)\\big\]=\[Wπ​\(τ′\)−g⁡\(y\)\]\+Vπ​\(y\)−Vπ​\(s\),=\\big\[W\_\{\\pi\}\(\\tau^\{\\prime\}\)\-g\(y\)\\big\]\+V^\{\\pi\}\(y\)\-V^\{\\pi\}\(s\),by telescoping the value terms\. SinceVπ​\(y\)=g​\(y\)V^\{\\pi\}\(y\)=g\(y\), this equalsWπ​\(τ′\)−Vπ​\(s\)W\_\{\\pi\}\(\\tau^\{\\prime\}\)\-V^\{\\pi\}\(s\)\. ∎

Part \(b\) has no classical counterpart\. It says that the deficit of*any*certified path relative to the value is exactly the sum of tropical advantages along it: a deterministic accounting, path by path, with no expectation\. Every path has non\-positive deficit because every tropical advantage is non\-positive, and the witness has deficit zero because every action on it is a maximizer\. The lemma is the reason the tropical advantage never needs to be estimated: it is a local quantity computable by the dynamic program, and on the path one trains it vanishes identically\.

###### Theorem 14\(Tropical performance difference lemma\)\.

For actorsπ,π′\\pi,\\pi^\{\\prime\}and a statesswithVπ′​\(s\)\>−∞V^\{\\pi^\{\\prime\}\}\(s\)\>\-\\infty, letτπ′⋆​\(s\)\\tau^\{\\star\}\_\{\\pi^\{\\prime\}\}\(s\)be a path attainingVπ′​\(s\)V^\{\\pi^\{\\prime\}\}\(s\)\. Then

Vπ′​\(s\)−Vπ​\(s\)=∑\(st,at\)∈τπ′⋆​\(s\)\[Aπ​\(st,at\)\+λ​log⁡π′​\(at∣st\)π⁡\(at∣st\)\]\.V^\{\\pi^\{\\prime\}\}\(s\)\-V^\{\\pi\}\(s\)=\\sum\_\{\(s\_\{t\},a\_\{t\}\)\\in\\tau^\{\\star\}\_\{\\pi^\{\\prime\}\}\(s\)\}\\Big\[A^\{\\pi\}\(s\_\{t\},a\_\{t\}\)\+\\lambda\\log\\frac\{\\pi^\{\\prime\}\(a\_\{t\}\\mid s\_\{t\}\)\}\{\\pi\(a\_\{t\}\\mid s\_\{t\}\)\}\\Big\]\.\(16\)

###### Proof\.

Rewards and terminal scores do not depend on the actor, so for any pathWπ′​\(τ′\)=Wπ​\(τ′\)\+λ​∑tlog⁡π′​\(at∣st\)π⁡\(at∣st\)W\_\{\\pi^\{\\prime\}\}\(\\tau^\{\\prime\}\)=W\_\{\\pi\}\(\\tau^\{\\prime\}\)\+\\lambda\\sum\_\{t\}\\log\\frac\{\\pi^\{\\prime\}\(a\_\{t\}\\mid s\_\{t\}\)\}\{\\pi\(a\_\{t\}\\mid s\_\{t\}\)\}\. Apply this toτ′=τπ′⋆​\(s\)\\tau^\{\\prime\}=\\tau^\{\\star\}\_\{\\pi^\{\\prime\}\}\(s\), which by Lemma[13](https://arxiv.org/html/2610.02478#Thmtheorem13)\(a\) satisfiesWπ′​\(τ′\)=Vπ′​\(s\)W\_\{\\pi^\{\\prime\}\}\(\\tau^\{\\prime\}\)=V^\{\\pi^\{\\prime\}\}\(s\)and has an accepted terminal, and expandWπ​\(τ′\)W\_\{\\pi\}\(\\tau^\{\\prime\}\)by Lemma[13](https://arxiv.org/html/2610.02478#Thmtheorem13)\(b\)\. ∎

Set the two lemmas side by side\. Classically,Vπ′​\(s\)−Vπ​\(s\)=𝔼τ∼π′​\[∑tAπ​\(st,at\)\]V^\{\\pi^\{\\prime\}\}\(s\)\-V^\{\\pi\}\(s\)=\\mathbb\{E\}\_\{\\tau\\sim\\pi^\{\\prime\}\}\[\\sum\_\{t\}A^\{\\pi\}\(s\_\{t\},a\_\{t\}\)\]: the old advantage, averaged over the new policy’s trajectories\. Tropically the average is over one path, and a second term appears, the log\-ratio of the two actors along it\. It appears because in tropical RL the per\-step reward is the actor’s own log\-likelihood, so changing the actor changes the rewards; there is no analogue in classical RL, where rewards are exogenous\. The log\-ratio that trust\-region methods introduce by hand as an importance weight is here part of the identity, additively, along a single path\.

###### Corollary 2\(Sandwich, and a witness for the slack\)\.

Under the hypotheses of Theorem[14](https://arxiv.org/html/2610.02478#Thmtheorem14), withτπ⋆​\(s\)\\tau^\{\\star\}\_\{\\pi\}\(s\)a path attainingVπ​\(s\)V^\{\\pi\}\(s\),

λ​∑\(st,at\)∈τπ⋆​\(s\)log⁡π′​\(at∣st\)π⁡\(at∣st\)≤Vπ′​\(s\)−Vπ​\(s\)≤λ​∑\(st,at\)∈τπ′⋆​\(s\)log⁡π′​\(at∣st\)π⁡\(at∣st\)\.\\lambda\\sum\_\{\(s\_\{t\},a\_\{t\}\)\\in\\tau^\{\\star\}\_\{\\pi\}\(s\)\}\\log\\frac\{\\pi^\{\\prime\}\(a\_\{t\}\\mid s\_\{t\}\)\}\{\\pi\(a\_\{t\}\\mid s\_\{t\}\)\}\\ \\leq\\ V^\{\\pi^\{\\prime\}\}\(s\)\-V^\{\\pi\}\(s\)\\ \\leq\\ \\lambda\\sum\_\{\(s\_\{t\},a\_\{t\}\)\\in\\tau^\{\\star\}\_\{\\pi^\{\\prime\}\}\(s\)\}\\log\\frac\{\\pi^\{\\prime\}\(a\_\{t\}\\mid s\_\{t\}\)\}\{\\pi\(a\_\{t\}\\mid s\_\{t\}\)\}\.\(17\)The slack of the left inequality isWπ′​\(τπ′⋆​\(s\)\)−Wπ′​\(τπ⋆​\(s\)\)≥0W\_\{\\pi^\{\\prime\}\}\(\\tau^\{\\star\}\_\{\\pi^\{\\prime\}\}\(s\)\)\-W\_\{\\pi^\{\\prime\}\}\(\\tau^\{\\star\}\_\{\\pi\}\(s\)\)\\geq 0, the amount by which the new witness beats the old witness under the new actor; the slack of the right inequality is−∑τπ′⋆​\(s\)Aπ\(st,at\)≥0\-\\sum\_\{\\tau^\{\\star\}\_\{\\pi^\{\\prime\}\}\(s\)\}A^\{\\pi\}\(s\_\{t\},a\_\{t\}\)\\geq 0, the old\-actor deficit of the new witness\.

###### Proof\.

Lower bound: by Lemma[13](https://arxiv.org/html/2610.02478#Thmtheorem13)\(a\),Vπ′​\(s\)≥Wπ′​\(τπ⋆​\(s\)\)=Wπ​\(τπ⋆​\(s\)\)\+λ​∑τπ⋆​\(s\)log⁡π′π=Vπ​\(s\)\+λ​∑τπ⋆​\(s\)log⁡π′πV^\{\\pi^\{\\prime\}\}\(s\)\\geq W\_\{\\pi^\{\\prime\}\}\(\\tau^\{\\star\}\_\{\\pi\}\(s\)\)=W\_\{\\pi\}\(\\tau^\{\\star\}\_\{\\pi\}\(s\)\)\+\\lambda\\sum\_\{\\tau^\{\\star\}\_\{\\pi\}\(s\)\}\\log\\frac\{\\pi^\{\\prime\}\}\{\\pi\}=V^\{\\pi\}\(s\)\+\\lambda\\sum\_\{\\tau^\{\\star\}\_\{\\pi\}\(s\)\}\\log\\frac\{\\pi^\{\\prime\}\}\{\\pi\}, and the slack isVπ′​\(s\)−Wπ′​\(τπ⋆​\(s\)\)=Wπ′​\(τπ′⋆​\(s\)\)−Wπ′​\(τπ⋆​\(s\)\)V^\{\\pi^\{\\prime\}\}\(s\)\-W\_\{\\pi^\{\\prime\}\}\(\\tau^\{\\star\}\_\{\\pi\}\(s\)\)=W\_\{\\pi^\{\\prime\}\}\(\\tau^\{\\star\}\_\{\\pi^\{\\prime\}\}\(s\)\)\-W\_\{\\pi^\{\\prime\}\}\(\\tau^\{\\star\}\_\{\\pi\}\(s\)\), nonnegative sinceτπ′⋆​\(s\)\\tau^\{\\star\}\_\{\\pi^\{\\prime\}\}\(s\)attains the maximum underπ′\\pi^\{\\prime\}\. Upper bound: drop the non\-positive advantages in equation[16](https://arxiv.org/html/2610.02478#A1.E16); the slack is their negative sum\. ∎

The lower bound is what TROPIC’s improvement step maximizes withπ=π¯t\\pi=\\bar\{\\pi\}\_\{t\}: the log\-likelihood gain on the current witness\. It is a valid lower bound on the true improvement for*any*π′\\pi^\{\\prime\}, with no penalty term\. A penalty\-free bound of this kind also exists for the hull distance, where it is the evidence lower bound; what is specific to the vertex distance is that both ends of the sandwich are single\-path log\-likelihood ratios and that the slack is not a divergence between posteriors but a concrete path, the new witness\. When discovery or composition has made a new path the best one under the new actor, that path is the slack, and the slack is the contribution of composition to improvement\. Nothing in the classical lemma isolates this quantity\.

###### Corollary 3\(Tropical policy gradient, and the classical weights\)\.

Let the actor be tabular softmax and let the maximizerτ⋆\\tau^\{\\star\}ofVπz​\(s0\)V^\{\\pi\_\{z\}\}\(s\_\{0\}\)be unique\. Then

∂Vπz​\(s0\)∂zs,a=\{λ\(𝟏\{a=a⋆\(s\)\}−πz\(a∣s\)\),s∈Sτ⋆,0,otherwise,\\frac\{\\partial V^\{\\pi\_\{z\}\}\(s\_\{0\}\)\}\{\\partial z\_\{s,a\}\}=\\begin\{cases\}\\lambda\\big\(\\mathbf\{1\}\\\{a=a^\{\\star\}\(s\)\\\}\-\\pi\_\{z\}\(a\\mid s\)\\big\),&s\\in S\_\{\\tau^\{\\star\}\},\\\\\[2\.0pt\] 0,&\\text\{otherwise\},\\end\{cases\}\(18\)wherea⋆​\(s\)a^\{\\star\}\(s\)is the action ofτ⋆\\tau^\{\\star\}atss\. For comparison, with zero internal reward and terminal rewardR∈\{0,1\}R\\in\\\{0,1\\\}, the expected\-return valueVπ¯​\(s0\)=∑τPz​\(τ\)​R​\(τ\)V^\{\\bar\{\\pi\}\}\(s\_\{0\}\)=\\sum\_\{\\tau\}P\_\{z\}\(\\tau\)R\(\\tau\)satisfies

∂Vπ¯​\(s0\)∂zs,a=dπ​\(s\)​πz​\(a∣s\)​AER​\(s,a\),AER​\(s,a\)=Vπ¯​\(T⁡\(s,a\)\)−Vπ¯​\(s\),\\frac\{\\partial V^\{\\bar\{\\pi\}\}\(s\_\{0\}\)\}\{\\partial z\_\{s,a\}\}=d^\{\\pi\}\(s\)\\,\\pi\_\{z\}\(a\\mid s\)\\,A\_\{\\mathrm\{ER\}\}\(s,a\),\\qquad A\_\{\\mathrm\{ER\}\}\(s,a\)=V^\{\\bar\{\\pi\}\}\(T\(s,a\)\)\-V^\{\\bar\{\\pi\}\}\(s\),\(19\)wheredπ​\(s\)d^\{\\pi\}\(s\)is the probability that a rollout froms0s\_\{0\}visitsss\.

###### Proof\.

For equation[18](https://arxiv.org/html/2610.02478#A1.E18), Corollary[1](https://arxiv.org/html/2610.02478#Thmcorollary1)\(b\) applies toWz​\(τ\)=∑t\[λ​log⁡πz​\(at∣st\)\+r⁡\(st,at\)\]\+g⁡\(y\)W\_\{z\}\(\\tau\)=\\sum\_\{t\}\[\\lambda\\log\\pi\_\{z\}\(a\_\{t\}\\mid s\_\{t\}\)\+r\(s\_\{t\},a\_\{t\}\)\]\+g\(y\), which is continuously differentiable inzz, and gives∇zVπz​\(s0\)=λ​∑\(st,at\)∈τ⋆∇z​log​πz​\(at∣st\)\\nabla\_\{z\}V^\{\\pi\_\{z\}\}\(s\_\{0\}\)=\\lambda\\sum\_\{\(s\_\{t\},a\_\{t\}\)\\in\\tau^\{\\star\}\}\\nabla\_\{z\}\\log\\pi\_\{z\}\(a\_\{t\}\\mid s\_\{t\}\)\. Since∂logπz\(at∣st\)/∂zs,a=𝟏\{s=st\}\(𝟏\{a=at\}−πz\(a∣s\)\)\\partial\\log\\pi\_\{z\}\(a\_\{t\}\\mid s\_\{t\}\)/\\partial z\_\{s,a\}=\\mathbf\{1\}\\\{s=s\_\{t\}\\\}\\big\(\\mathbf\{1\}\\\{a=a\_\{t\}\\\}\-\\pi\_\{z\}\(a\\mid s\)\\big\)and a path visits each state at most once, the stated formula follows\.

For equation[19](https://arxiv.org/html/2610.02478#A1.E19),∂logPz\(τ\)/∂zs,a=𝟏\{s∈Sτ\}\(𝟏\{aτ\(s\)=a\}−πz\(a∣s\)\)\\partial\\log P\_\{z\}\(\\tau\)/\\partial z\_\{s,a\}=\\mathbf\{1\}\\\{s\\in S\_\{\\tau\}\\\}\\big\(\\mathbf\{1\}\\\{a\_\{\\tau\}\(s\)=a\\\}\-\\pi\_\{z\}\(a\\mid s\)\\big\), so

∂Vπ¯​\(s0\)∂zs,a=∑τ∋sPz\(τ\)R\(τ\)\(𝟏\{aτ\(s\)=a\}−πz\(a∣s\)\)\.\\frac\{\\partial V^\{\\bar\{\\pi\}\}\(s\_\{0\}\)\}\{\\partial z\_\{s,a\}\}=\\sum\_\{\\tau\\ni s\}P\_\{z\}\(\\tau\)R\(\\tau\)\\big\(\\mathbf\{1\}\\\{a\_\{\\tau\}\(s\)=a\\\}\-\\pi\_\{z\}\(a\\mid s\)\\big\)\.Every path throughssfactors as a prefix froms0s\_\{0\}toss, an action atss, and a suffix fromT​\(s,aτ​\(s\)\)T\(s,a\_\{\\tau\}\(s\)\), withPz​\(τ\)=Pz​\(prefix\)​πz​\(aτ​\(s\)∣s\)​Pz​\(suffix\)P\_\{z\}\(\\tau\)=P\_\{z\}\(\\text\{prefix\}\)\\pi\_\{z\}\(a\_\{\\tau\}\(s\)\\mid s\)P\_\{z\}\(\\text\{suffix\}\)andR⁡\(τ\)R\(\\tau\)determined by the suffix\. Summing over prefixes givesdπ​\(s\)d^\{\\pi\}\(s\)and summing over suffixes givesVπ¯V^\{\\bar\{\\pi\}\}of the successor, so∑τ∋s,aτ​\(s\)=aPz​\(τ\)​R​\(τ\)=dπ​\(s\)​πz​\(a∣s\)​Vπ¯​\(T⁡\(s,a\)\)\\sum\_\{\\tau\\ni s,\\,a\_\{\\tau\}\(s\)=a\}P\_\{z\}\(\\tau\)R\(\\tau\)=d^\{\\pi\}\(s\)\\pi\_\{z\}\(a\\mid s\)V^\{\\bar\{\\pi\}\}\(T\(s,a\)\)and∑τ∋sPz​\(τ\)​R​\(τ\)=dπ​\(s\)​Vπ¯​\(s\)\\sum\_\{\\tau\\ni s\}P\_\{z\}\(\\tau\)R\(\\tau\)=d^\{\\pi\}\(s\)V^\{\\bar\{\\pi\}\}\(s\)\. Substituting,

∂Vπ¯​\(s0\)∂zs,a=dπ​\(s\)​πz​\(a∣s\)​Vπ¯​\(T⁡\(s,a\)\)−πz​\(a∣s\)​dπ​\(s\)​Vπ¯​\(s\)=dπ​\(s\)​πz​\(a∣s\)​AER​\(s,a\)\.\\frac\{\\partial V^\{\\bar\{\\pi\}\}\(s\_\{0\}\)\}\{\\partial z\_\{s,a\}\}=d^\{\\pi\}\(s\)\\pi\_\{z\}\(a\\mid s\)V^\{\\bar\{\\pi\}\}\(T\(s,a\)\)\-\\pi\_\{z\}\(a\\mid s\)d^\{\\pi\}\(s\)V^\{\\bar\{\\pi\}\}\(s\)=d^\{\\pi\}\(s\)\\pi\_\{z\}\(a\\mid s\)A\_\{\\mathrm\{ER\}\}\(s,a\)\.∎

The two formulas differ in exactly the way the two performance difference lemmas differ\. The classical gradient at\(s,a\)\(s,a\)carries the probability of reachingss, the probability of takingaa, and, insideAERA\_\{\\mathrm\{ER\}\}, the probability of completing the task afterwards\. On a path whose steps each have probabilityρ\\rho, every one of these factors is a power ofρ\\rhoand the gradient at every logit on the path is of orderρd\\rho^\{d\}\. The tropical gradient on the witness carries none of them: it isλ⁡\(𝟏−π\)\\lambda\(\\mathbf\{1\}\-\\pi\), of order one however improbable the path\. Natural policy gradient removes the upstream factor by preconditioning and keeps the completion factor; the tropical gradient removes both, because the path it differentiates is certified and its advantage is identically zero\. The next theorem turns this into a rate separation on the simplest instance, with exact gradients, so that neither sampling noise nor value estimation is involved\.

###### Theorem 15\(Exponential versus logarithmic escape on a chain\)\.

Let the graph be a chains0→s1→…→sds\_\{0\}\\to s\_\{1\}\\to\\dots\\to s\_\{d\}, where at eachsks\_\{k\}\(k<dk<d\) the actiona⋆a^\{\\star\}leads tosk\+1s\_\{k\+1\}and the actiona′a^\{\\prime\}leads to a rejected terminal, andsds\_\{d\}is an accepted terminal\. Let the actor be tabular softmax with one free logit per state,πk=π⁡\(a⋆∣sk\)=σ⁡\(zk\)\\pi\_\{k\}=\\pi\(a^\{\\star\}\\mid s\_\{k\}\)=\\sigma\(z\_\{k\}\), initialized atπk\(0\)=ρ≤12\\pi\_\{k\}^\{\(0\)\}=\\rho\\leq\\tfrac\{1\}\{2\}for allkk, and takeλ=1\\lambda=1,r≡0r\\equiv 0\. Consider gradient ascent with stepη\>0\\eta\>0on the logits\.

1. \(a\)\(Expected return\.\)ForJER​\(z\)=Vπ¯​\(s0\)=∏k<dπkJ\_\{\\mathrm\{ER\}\}\(z\)=V^\{\\bar\{\\pi\}\}\(s\_\{0\}\)=\\prod\_\{k<d\}\\pi\_\{k\}, the first iterationNNat whichJER≥2​ρdJ\_\{\\mathrm\{ER\}\}\\geq 2\\rho^\{d\}satisfies N\>log⁡22​d​η​ρd\.N\>\\frac\{\\log 2\}\{2\\,d\\,\\eta\\,\\rho^\{d\}\}\.
2. \(b\)\(Tropical\.\)ForJtrop​\(z\)=Vtropπ¯​\(s0\)=∑k<dlog⁡πkJ\_\{\\mathrm\{trop\}\}\(z\)=V^\{\\bar\{\\pi\}\}\_\{\\mathrm\{trop\}\}\(s\_\{0\}\)=\\sum\_\{k<d\}\\log\\pi\_\{k\}, afterN0=⌈2η​log⁡1ρ⌉N\_\{0\}=\\lceil\\tfrac\{2\}\{\\eta\}\\log\\tfrac\{1\}\{\\rho\}\\rceiliterations everyπk≥12\\pi\_\{k\}\\geq\\tfrac\{1\}\{2\}, soJtrop≥−d​log⁡2J\_\{\\mathrm\{trop\}\}\\geq\-d\\log 2, and for everyn\>N0n\>N\_\{0\}, −Jtrop\(n\)<2​dη⁡\(n−N0\)\.\-J\_\{\\mathrm\{trop\}\}^\{\(n\)\}<\\frac\{2d\}\{\\eta\\,\(n\-N\_\{0\}\)\}\.

The bound in \(a\) is exponential indd; the bound in \(b\) is logarithmic in1/ρ1/\\rhoand independent ofdd, followed by a1/n1/nrate\.

###### Proof\.

\(a\) Sincelog⁡πk=log⁡σ⁡\(zk\)\\log\\pi\_\{k\}=\\log\\sigma\(z\_\{k\}\)anddd​z​log⁡σ⁡\(z\)=1−σ⁡\(z\)\\frac\{d\}\{dz\}\\log\\sigma\(z\)=1\-\\sigma\(z\),

∂JER∂zk=JER​∂log⁡JER∂zk=JER​\(1−πk\)∈\(0,JER\)\.\\frac\{\\partial J\_\{\\mathrm\{ER\}\}\}\{\\partial z\_\{k\}\}=J\_\{\\mathrm\{ER\}\}\\,\\frac\{\\partial\\log J\_\{\\mathrm\{ER\}\}\}\{\\partial z\_\{k\}\}=J\_\{\\mathrm\{ER\}\}\(1\-\\pi\_\{k\}\)\\in\(0,J\_\{\\mathrm\{ER\}\}\)\.Hence eachzkz\_\{k\}, eachπk\\pi\_\{k\}andJERJ\_\{\\mathrm\{ER\}\}are non\-decreasing along the iteration, and at any iterationnnwithJER\(n\)<2​ρdJ^\{\(n\)\}\_\{\\mathrm\{ER\}\}<2\\rho^\{d\}every logit moves by less than2​η​ρd2\\eta\\rho^\{d\}\. The functionlog⁡σ\\log\\sigmais concave, so forΔ\>0\\Delta\>0,log⁡σ⁡\(z\+Δ\)−log⁡σ⁡\(z\)≤Δ⁡\(1−σ⁡\(z\)\)≤Δ\\log\\sigma\(z\+\\Delta\)\-\\log\\sigma\(z\)\\leq\\Delta\\,\(1\-\\sigma\(z\)\)\\leq\\Delta\. Therefore, at any such iteration,

log⁡JER\(n\+1\)−log⁡JER\(n\)=∑k<d\[log⁡πk\(n\+1\)−log⁡πk\(n\)\]<2​d​η​ρd\.\\log J^\{\(n\+1\)\}\_\{\\mathrm\{ER\}\}\-\\log J^\{\(n\)\}\_\{\\mathrm\{ER\}\}=\\sum\_\{k<d\}\\big\[\\log\\pi^\{\(n\+1\)\}\_\{k\}\-\\log\\pi^\{\(n\)\}\_\{k\}\\big\]<2\\,d\\,\\eta\\,\\rho^\{d\}\.All iterations beforeNNhaveJER<2​ρdJ\_\{\\mathrm\{ER\}\}<2\\rho^\{d\}, so summing,log⁡JER\(N\)−log⁡JER\(0\)<2​d​η​ρd​N\\log J^\{\(N\)\}\_\{\\mathrm\{ER\}\}\-\\log J^\{\(0\)\}\_\{\\mathrm\{ER\}\}<2d\\eta\\rho^\{d\}N\. SinceJER\(0\)=ρdJ^\{\(0\)\}\_\{\\mathrm\{ER\}\}=\\rho^\{d\}andJER\(N\)≥2​ρdJ^\{\(N\)\}\_\{\\mathrm\{ER\}\}\\geq 2\\rho^\{d\}, the left side is at leastlog⁡2\\log 2, which gives the claim\.

\(b\) Here∂Jtrop/∂zk=1−πk=σ⁡\(−zk\)\\partial J\_\{\\mathrm\{trop\}\}/\\partial z\_\{k\}=1\-\\pi\_\{k\}=\\sigma\(\-z\_\{k\}\), sozk\(n\+1\)=zk\(n\)\+η​σ​\(−zk\(n\)\)z^\{\(n\+1\)\}\_\{k\}=z^\{\(n\)\}\_\{k\}\+\\eta\\,\\sigma\(\-z^\{\(n\)\}\_\{k\}\)and eachzkz\_\{k\}is increasing\. The coordinates evolve independently and identically, so fixkk\.

Phase one\. Whilezk\(n\)<0z^\{\(n\)\}\_\{k\}<0we haveσ⁡\(−zk\(n\)\)\>12\\sigma\(\-z^\{\(n\)\}\_\{k\}\)\>\\tfrac\{1\}\{2\}, sozk\(n\+1\)−zk\(n\)\>η/2z^\{\(n\+1\)\}\_\{k\}\-z^\{\(n\)\}\_\{k\}\>\\eta/2\. The initial logit iszk\(0\)=log⁡ρ1−ρ≥log⁡ρ=−log⁡1ρz^\{\(0\)\}\_\{k\}=\\log\\frac\{\\rho\}\{1\-\\rho\}\\geq\\log\\rho=\-\\log\\frac\{1\}\{\\rho\}, sinceρ1−ρ≥ρ\\frac\{\\rho\}\{1\-\\rho\}\\geq\\rho\. Hencezkz\_\{k\}reaches00within at most⌈log⁡\(1/ρ\)η/2⌉=N0\\lceil\\frac\{\\log\(1/\\rho\)\}\{\\eta/2\}\\rceil=N\_\{0\}iterations, and, being increasing, stays nonnegative thereafter\. Thusπk\(n\)≥12\\pi^\{\(n\)\}\_\{k\}\\geq\\tfrac\{1\}\{2\}for alln≥N0n\\geq N\_\{0\}andJtrop\(N0\)≥−d​log⁡2J^\{\(N\_\{0\}\)\}\_\{\\mathrm\{trop\}\}\\geq\-d\\log 2\.

Phase two\. Forz≥0z\\geq 0,1\+ez≤2​ez1\+e^\{z\}\\leq 2e^\{z\}, soσ⁡\(−z\)=11\+ez≥12​e−z\\sigma\(\-z\)=\\frac\{1\}\{1\+e^\{z\}\}\\geq\\tfrac\{1\}\{2\}e^\{\-z\}\. Letyn=ezk\(n\)y\_\{n\}=e^\{z^\{\(n\)\}\_\{k\}\}forn≥N0n\\geq N\_\{0\}, soyN0≥1y\_\{N\_\{0\}\}\\geq 1\. Usingex≥1\+xe^\{x\}\\geq 1\+x,

yn\+1=yn​ezk\(n\+1\)−zk\(n\)≥yn​\(1\+η​σ​\(−zk\(n\)\)\)≥yn​\(1\+η2​yn\)=yn\+η2\.y\_\{n\+1\}=y\_\{n\}e^\{z^\{\(n\+1\)\}\_\{k\}\-z^\{\(n\)\}\_\{k\}\}\\geq y\_\{n\}\\big\(1\+\\eta\\,\\sigma\(\-z^\{\(n\)\}\_\{k\}\)\\big\)\\geq y\_\{n\}\\Big\(1\+\\frac\{\\eta\}\{2y\_\{n\}\}\\Big\)=y\_\{n\}\+\\frac\{\\eta\}\{2\}\.Henceyn≥1\+η2​\(n−N0\)y\_\{n\}\\geq 1\+\\frac\{\\eta\}\{2\}\(n\-N\_\{0\}\)forn≥N0n\\geq N\_\{0\}\. Finally−log⁡πk\(n\)=log⁡\(1\+e−zk\(n\)\)≤e−zk\(n\)=1/yn≤\(1\+η2​\(n−N0\)\)−1<2η⁡\(n−N0\)\-\\log\\pi^\{\(n\)\}\_\{k\}=\\log\(1\+e^\{\-z^\{\(n\)\}\_\{k\}\}\)\\leq e^\{\-z^\{\(n\)\}\_\{k\}\}=1/y\_\{n\}\\leq\\big\(1\+\\tfrac\{\\eta\}\{2\}\(n\-N\_\{0\}\)\\big\)^\{\-1\}<\\frac\{2\}\{\\eta\(n\-N\_\{0\}\)\}forn\>N0n\>N\_\{0\}\. Summing over theddcoordinates gives the bound\. ∎

### A\.6How TROPIC realizes these results

The algorithm of Section[4\.3](https://arxiv.org/html/2610.02478#S4.SS3)is the loop these results describe\. The archive is the set of certified vertices of Section[A\.2](https://arxiv.org/html/2610.02478#A1.SS2); discovery adds vertices and composition adds vertices assembled from existing ones, and by Theorem[3](https://arxiv.org/html/2610.02478#Thmtheorem3)the set never shrinks\. Rescoring under the frozen actor recomputes the distances from the current actor to each vertex\. Corollary[1](https://arxiv.org/html/2610.02478#Thmcorollary1)\(a\) is why the prefix and suffix passes may be run separately and joined\. The improvement step is maximum likelihood on that nearest vertex, which Corollary[1](https://arxiv.org/html/2610.02478#Thmcorollary1)\(b\) identifies as the exact gradient of the tropical value, Corollary[2](https://arxiv.org/html/2610.02478#Thmcorollary2)identifies as maximizing a penalty\-free lower bound on the true improvement, and Theorem[12](https://arxiv.org/html/2610.02478#Thmtheorem12)shows to be a pointwise improvement step on the whole retained graph\. By Theorem[7](https://arxiv.org/html/2610.02478#Thmtheorem7)and Proposition[3](https://arxiv.org/html/2610.02478#Thmproposition3)the step depends on the archive only through its support, which is why acquisition may be as off\-policy as the frontier rule makes it, with no correction\. By Proposition[4](https://arxiv.org/html/2610.02478#Thmproposition4)it is not a step that expected\-return information could have selected\. What the actor is pulled toward, at every iteration and at every interface, is the nearest computation it has been shown to be capable of; what it is never pulled toward is a distribution over computations, and what it is never allowed to lose is a computation it has already been shown\.

## Appendix BRL Environments

![Refer to caption](https://arxiv.org/html/2610.02478v1/Images/environments_row.png)Figure 5:Environments\.From left to right:Sokoban, push the box onto the target without creating a dead end;FrozenLake, reach the goal without stepping into a hole;WebShop, search for and purchase a product that matches a natural\-language instruction; andCountdown, combine the given numbers with arithmetic operations to reach the target, here\(97−40\)/\(14−11\)=19\(97\-40\)/\(14\-11\)=19\.All four environments in Fig\.[5](https://arxiv.org/html/2610.02478#A2.F5)are multi\-turn agentic tasks from RAGEN\-2\([Wang et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib11)\)\. In each, the agent observes a text rendering of the current environment state, emits an action, and receives a binary verifier signal only at the end of the episode\. As described in the main body,Tropicprompts the actor with the problem and the current environment state only, and includes the step count in the state so that the graph of states is acyclic\. Two attempts therefore share a state whenever they reach the same environment configuration at the same step, even if they got there by different actions\. These shared states are the interfaces at whichTropicjoins a prefix from one attempt with a suffix from another\. For every task, we describe below what a state is, what the verifier checks, and why such interfaces arise\.

#### Sokoban\.

The agent moves on a6×66\\times 6grid and must push a single box onto a target cell\. A state is the board configuration, i\.e\., the positions of the agent and the box\. An episode succeeds when the box rests on the target\. Pushing the box against a wall or into a corner can make the puzzle unsolvable, so many attempts fail late after a sequence of correct early pushes\. For expected\-return methods, such attempts yield zero reward and their correct prefixes receive no credit\.Tropickeeps these prefixes in its graph: if another attempt, started from the same board configuration, reaches the target, the two are joined into a verified solution that neither attempt produced alone\. Because different move orders often lead to the same board, such shared configurations are frequent\.

#### Countdown\.

The agent is given three to six input numbers and a target, and must combine the numbers with\+\+,−\-,×\\times, and÷\\div, using each number exactly once, to reach the target\. A state is the multiset of numbers still available, and each step replaces two numbers by the result of an operation on them\. The verifier checks that the final number equals the target\. Because arithmetic steps on disjoint numbers commute, different attempts frequently reach the same intermediate multiset, e\.g\.,\{57,3\}\\\{57,3\\\}from97−4097\-40and14−1114\-11in either order\. An attempt that computes a useful intermediate result but then fails, and another that finishes correctly from the same intermediate multiset, can therefore be joined into a verified derivation\. Training and evaluation use disjoint problem splits\.

#### FrozenLake\.

The agent navigates a4×44\\times 4grid from a start cell to a goal cell while avoiding holes, which end the episode\. Each cell is safe with probability0\.90\.9when the map is generated, and transitions are deterministic in our experiments\. A state is the agent’s position\. Success requires an entire sequence of safe moves, and a single misstep anywhere ends the episode with zero reward, so failed attempts often contain long safe prefixes\.Tropicretains these prefixes and restarts new attempts from the frontier of safe cells, so a safe route to the middle of the grid found in one attempt can be completed by a suffix found in another\.

#### WebShop\.

The agent receives a natural\-language shopping instruction, e\.g\., a portable folding desk with a given finish below a price limit, and must search the catalog, navigate result and product pages, select the required attributes, and purchase a matching item\. We use the RAGEN\-2webshop\-minimaladaptation\. A state is the current page together with the selections made so far\. An episode succeeds only if the purchased item satisfies all requested attributes\. Episodes are long, and a mistake late in the episode, such as a wrong attribute, discards an otherwise correct search and navigation\.Tropickeeps the correct search and navigation steps and can join them with a correct selection\-and\-purchase suffix found in another attempt from the same product page\.

#### Why these Tasks Favor Composition\.

The four environments share the structure that makes expected return inefficient and tropical composition effective: the reward is sparse and terminal, failures typically occur after many correct steps, and different attempts pass through the same intermediate states\. On\-policy baselines must sample a complete successful episode before any of its steps is reinforced\.Tropicinstead retains every valid step, including steps from failed attempts, and assembles verified solutions at shared states\. This is the mechanism measured directly byFirst\-Solvein Sec\.[6\.1](https://arxiv.org/html/2610.02478#S6.SS1)\.

## Appendix CTraining and Evaluation Setup

Our implementation builds on RAGEN\-2\([Wang et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib11)\)and its VERL training backend\([Sheng et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib3)\)\. We follow the default RAGEN\-2 configuration where applicable and describe all task\- and method\-specific settings below\.

#### Models\.

We initialize all policies from Qwen2\.5\-3B\-Instruct\([Qwen et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib6)\), with3\.13\.1B parameters, and Gemma\-4\-E4B\-it\([Gemma Team, 2026](https://arxiv.org/html/2610.02478#bib.bib1)\), with44B effective and88B total parameters including embeddings, i\.e\., more than twice as many parameters in total\. The two models also differ in family, architecture, and pretraining data, which lets us test whetherTropic’s gains depend on a particular model\. All models are fully fine\-tuned without parameter\-efficient adapters\.

#### Baselines\.

We compare against PPO\([Schulman et al\., 2017](https://arxiv.org/html/2610.02478#bib.bib5)\), GRPO\([Shao et al\., 2024](https://arxiv.org/html/2610.02478#bib.bib36)\), DAPO\([Yu et al\., 2025](https://arxiv.org/html/2610.02478#bib.bib4)\), and RAGEN\-2’s SNR\-Aware Filtering\([Wang et al\., 2026](https://arxiv.org/html/2610.02478#bib.bib11)\)\. All use AdamW with an actor learning rate of10−610^\{\-6\},\(β1,β2\)=\(0\.9,0\.999\)\(\\beta\_\{1\},\\beta\_\{2\}\)=\(0\.9,0\.999\), and weight decay0\.010\.01\. PPO and SNR\-Aware use a learned critic with learning rate10−510^\{\-5\}and Generalized Advantage Estimation\([Schulman et al\., 2018](https://arxiv.org/html/2610.02478#bib.bib2)\)withγ=1\\gamma=1andλGAE=1\\lambda\_\{\\mathrm\{GAE\}\}=1\. GRPO and DAPO use group\-relative advantages without a critic\. For DAPO we use the standard implementation provided by RAGEN\-2\. The policy\-ratio clipping interval is\[0\.8,1\.28\]\[0\.8,1\.28\], entropy regularization uses coefficient0\.0010\.001, and no reference\-policy KL penalty is applied\. SNR\-Aware Filtering applies the RAGEN\-2 rollout\-group filter with cumulative probability thresholdp=0\.9p=0\.9, using the within\-group reward standard deviation as its selection score\. The other baselines apply no rollout filtering\. The additional methods in Table[3](https://arxiv.org/html/2610.02478#S6.T3)\(MaxRL, GiGPO, and GiGPO \+ T\-STAR\) use the same backbone, optimizer, and rollout budget, with the remaining hyperparameters set as recommended by their authors\.

#### Tropic\.

Tropicuses the same AdamW optimizer and actor learning rate \(10−610^\{\-6\}\) as the baselines, and performs maximum\-likelihood updates on verified paths\. It uses no critic, policy\-ratio clipping, entropy regularization, or reference\-policy KL penalty\. Each active training problem receivesG=2G=2sequential groups ofn=8n=8attempts per iteration\. The first group starts from the initial state; subsequent groups start from a selected frontier state when available, otherwise falling back to the initial state\. The resultingG​n=16Gn=16rollout starts per problem match the baselines’ nominal attempt budget; this does not imply equal generated\-token counts or verification costs\. Valid transitions are retained up to the graph capacity even when the originating attempt fails, but only complete paths replayed from the initial state and accepted by the verifier are eligible as training targets\. Graph memory persists across iterations over a recurring pool of 128 training problems, with eight problems visited per iteration\. Table[4](https://arxiv.org/html/2610.02478#A3.T4)lists theTropic\-specific settings for the main experiments\.

Table 4:Tropichyperparameters\.Shared across tasks and models unless stated otherwise\.HyperparameterDescriptionValueGGAttempt groups per problem/iteration22nnAttempts per group88κ\\kappaFrontier exploration weight1\.01\.0\-\-Training\-rollout temperature1\.01\.0LLPrefixes and suffixes per shared state44each\-\-Composition candidates per problem/refresh6464\-\-Maximum retained edges per problem1,0241\{,\}024\-\-Maximum archived solutions per problem6464\-\-Edge\-rescoring batch size6464KKMaximum training paths per problem22\-\-Coverage\-based path selectionEnabled\-\-Update epochs per iteration22\-\-Recurring training\-problem pool size128128

Composition is performed after each attempt group, giving two refreshes per iteration and at most2×64=1282\\times 64=128composition replays per active problem per iteration\. This limit does not include verification of sampled successful paths or any additional restart\-prefix checks\.

#### Training and Infrastructure\.

All experiments run on 8 NVIDIA A100 GPUs using Fully Sharded Data Parallel \(FSDP\) training with BF16 mixed precision\. Rollouts are generated with vLLM, and distributed execution is coordinated through Ray\. The optimization mini\-batch size is 32 sequences, i\.e\., four sequences per GPU, with gradient accumulation where necessary\. All methods train for at most 200 rollout–update iterations on Sokoban, Countdown, and FrozenLake, and at most 100 on WebShop\. Validation is performed before training and every 25 iterations\.

#### Evaluation Protocol\.

Final evaluation uses a fixed set of 512 held\-out instances per environment that are not seen during training\. Decoding uses temperatureT=0\.5T=0\.5, top\-p=1p=1, and no top\-kktruncation\. At evaluation time,Tropicuses no archive, restarts, or composition: the trained policy must solve each instance in a single attempt, exactly like the baselines, so the score measures what training has transferred into the model\. Each method is evaluated at its final checkpoint, and we report the mean and standard deviation across three independent training seeds\.

#### Metrics\.

We report the following metrics\.

1. 1\.Success rate\.The fraction of evaluation instances solved in a single attempt\. Success means placing the box on the target in Sokoban, satisfying the arithmetic verifier in Countdown, reaching the goal in FrozenLake, and completing a fully correct purchase in WebShop\.
2. 2\.pass@kk\.The probability that at least one ofkkattempts solves an evaluation instance \(see Fig\.[1](https://arxiv.org/html/2610.02478#S1.F1)\)\.
3. 3\.Generated tokens per episode\.The number of tokens generated across all turns of an evaluation episode, averaged over successful and unsuccessful episodes\. We use each model’s tokenizer and exclude prompts, environment observations, and padding\. This metric measures inference cost only\.
4. 4\.Training wall\-clock time\.The elapsed time from the start to the end of training, including rollout generation, optimization, scheduled validation, and checkpointing, and excluding external environment setup and checkpoint preparation\.
5. 5\.First\-Solve\(ablations only\)\. The fraction of solved training instances whose first verified solution was assembled by composition before any complete successful trajectory had been sampled\. By definition, it is zero for*No Composition*, which does not compose, and for*Successful\-Only*, which composes only from already successful trajectories\.

#### What the Evaluation Measures\.

We use*compositional*as described in the main body: a solution is compositional when its fragments have been produced in separate attempts but never together in a single one\.Tropictargets exactly this situation during training, andFirst\-Solvemeasures it directly\. On Sokoban,31\.6%31\.6\\%of solved training problems are first solved by a composition never sampled end to end\. The held\-out evaluation asks a separate question: whether the policy trained on these assembled solutions solves new instances on its own, in one attempt, without any ofTropic’s search machinery\. Since every held\-out instance is unseen during training, success requires producing a new solution rather than recalling a stored one\. We do not claim systematic generalization in the sense of[Lake and Baroni \(2018\)](https://arxiv.org/html/2610.02478#bib.bib44), i\.e\., to problems drawn from a different distribution of compositions, and leave such splits to future work\.

#### On the Fairness of the Comparison\.

Tropicdiffers from the baselines in three respects that could affect the comparison: it restarts attempts from frontier states, it replays and verifies composed paths, and it uses its own stopping rule\. We address each in turn\.

*Frontier restarts\.*Restarting from a frontier state requires a deterministic, resettable environment\. We regard this as the settingTropicis designed for, not an advantage granted to it\. To check that restarts alone do not explain the gains, the ablations in Table[3](https://arxiv.org/html/2610.02478#S6.T3)separate them from composition\.Tropic\(No Composition\) keeps the archive and frontier restarts and trains by maximum likelihood on sampled verified paths, which makes it closely related to archive\-based exploration combined with rejection\-sampling fine\-tuning\. It reaches40\.8%40\.8\\%on Sokoban, on par with the strongest baseline \(SNR\-Aware,42\.2%42\.2\\%\)\. Conversely,Tropic\(Root\-Only\) removes frontier restarts but keeps composition, and reaches51\.8%51\.8\\%, above every baseline\. The improvement therefore comes from composing fragments across attempts, not from restarts\.

*Replay and verification\.*Replaying a composed path executes its stored actions in the environment and queries the verifier\. Accordingly, it generates no tokens\. Since all methods generate the same number of rollouts per iteration, replay adds only environment calls, which are inexpensive relative to generation in all four tasks\.

*Stopping and Wall\-Clock Time\.*All methods share the same iteration cap\. The baselines stop according to RAGEN\-2’s criteria, whileTropicstops early when no training problem yields a new update\. Reported wall\-clock times therefore reflect the end\-to\-end cost of each method under its standard protocol, not a comparison at matched compute\. This does not favorTropic\. Since no method can exceed the shared cap, early stopping can only shortenTropic’s training, never extend it, and each baseline trains for as long as its standard protocol allows\. Running every method under its standard protocol is also the setting in which a practitioner would compare them\. Success rates are unaffected by this difference: all methods are evaluated at their final checkpoint on the same held\-out instances\.

## Appendix DLimitations

Tropical RL changes a single operation of reinforcement learning: alternative trajectories are combined by a maximum instead of a sum\. This one change gives the value three properties that expected return lacks\. It names a concrete path, it never decreases as new verified paths are found, and it splits into a best prefix and a best suffix at any shared state\.Tropicuses these properties to assemble solutions from fragments the actor never produced together\. On four agentic tasks, this translates into higher single\-attempt success than on\-policy baselines\.

It is worth being precise about the guarantee\. The archive, and the capability it certifies, never shrink\. For an actor with separate parameters per state, one step on the best path raises the tropical value of every state in the graph \(Theorem[4](https://arxiv.org/html/2610.02478#Thmtheorem4)\)\. A language model, however, shares parameters across states and problems, so a step on one problem can still lower the likelihood of a verified path on another\. The coverage paths of Section[4\.3](https://arxiv.org/html/2610.02478#S4.SS3)mitigate this, but they are a heuristic, not a proof\.Tropictherefore guarantees that no verified computation is lost from*memory*, not that the*actor*never forgets\.

This distinction points to the direction we find most promising: continual self\-improvement, in which a capability, once verified, is kept and becomes reusable by later ones\. Expected return has no mechanism for this, since it stores discoveries only in current probabilities and normalization makes them compete \(Proposition[1](https://arxiv.org/html/2610.02478#Thmproposition1)\)\. The tropical value provides the missing bookkeeping: a set of verified computations that only grows and whose best elements compose\. Whether this record can be transferred into shared weights without interference, at scale, remains open\.