Tropical Reinforcement Learning

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

cs.AIOct 1, 2026

Tropical Reinforcement Learning

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

Organizations: MBZUAI · TUM

Abstract

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

Figures & tables

Figure 2: A difference between expected $V$ and max $M$ continuation.

Figure 3: Lemma 3 schematic illustration

	Classical (sum)	Tropical (max)
The value measures	how much of the actor already succeeds	how far the actor is from its nearest verified solution (Lem. 5 )
Advantage	relative to the average action, must be estimated	$\leq 0$ , exactly $0$ on the best path, computed by the DP
Performance difference	expectation over the new policy’s trajectories	a sum over one path (Thm. 14 )
Gradient weight on a step	visit prob. $\times$ action prob. $\times$ completion prob.	$1$ on every step of the best path (Cor. 3 )
Rare path of depth $d$	escape takes $\sim\rho^{-d}$ steps	$O(\log\tfrac{1}{\rho})$ steps; MaxRL matches this on one path (Thm. 15 )
Training on one path	can lower an unsampled solution (Prop. 1 )	never lowers any state; shared parts gain in full (Thm. 4 )

Table 1: Classical and tropical RL on the same verified paths. Proofs in Appendix A .

Figure 4: Tropic performance against the baselines under the same compute budget.

Task	Method	Qwen2.5-3B-Instruct			Gemma 4 E4B-it
Task	Method	Success Rate ( $\uparrow$ )	Tokens ( $\downarrow$ )	Time (h) ( $\downarrow$ )	Success Rate ( $\uparrow$ )	Tokens ( $\downarrow$ )	Time (h) ( $\downarrow$ )
Sokoban	Base Model	12.89	254	--	45.50	205	--
	PPO	21.90 $\pm$ 2.14	231	2.70	71.68 $\pm$ 1.71	209	8.85
	GRPO	27.60 $\pm$ 2.47	205	2.90	66.53 $\pm$ 2.32	254	8.20
	DAPO	36.55 $\pm$ 2.11	174	2.80	72.65 $\pm$ 1.35	219	8.40
	SNR-Aware	42.20 $\pm$ 1.96	201	2.10	76.55 $\pm$ 1.94	237	8.30

Table 2: Results (Qwen2.5-3B-Instruct & Gemma 4 E4B-it). We report Success Rate (

\uparrow

, mean

\pm

standard 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

Method	Success Rate ( $\uparrow$ )	Tokens ( $\downarrow$ )	Time (h) ( $\downarrow$ )	First-Solve ( $\uparrow$ )
Base Model	12.89	254	--	--
MaxRL	51.30 $\pm$ 2.31	202	2.53	--
GiGPO	47.60 $\pm$ 2.18	199	3.11	--
GiGPO + T-STAR	53.10 $\pm$ 2.18	194	3.80	--
TROPIC (No Comp.)	40.80 $\pm$ 2.26	205	1.45	0.0
TROPIC (Root-Only)	51.80 $\pm$ 2.12	196	1.92	24.7 $\pm$ 3.2

Table 3: Ablations and Cross-Comparison (Sokoban, Qwen2.5-3B-Instruct). Success rate, tokens per episode, training time, and First-Solve .

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

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; and Countdown , combine the given numbers with arithmetic operations to reach the target, here $(97-40)/(14-11)=19$ .

Hyperparameter	Description	Value
$G$	Attempt groups per problem/iteration	$2$
$n$	Attempts per group	$8$
$\kappa$	Frontier exploration weight	$1.0$
--	Training-rollout temperature	$1.0$
$L$	Prefixes and suffixes per shared state	$4$ each
--	Composition candidates per problem/refresh	$64$

Appendix

Table 4: Tropic hyperparameters. Shared across tasks and models unless stated otherwise.

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,742 papers

Tandem Reinforcement Learning with Verifiable Rewards
Jun 26, 2026Difan Jiao, Raghav Singhal, Robert West +1Reinforcement Learning RL for Language Model Reasoning
University of Toronto · EPFL
Compositional Reasoning in Language Models under Reinforcement Learning Post-Training
Sep 16, 2026Yu He, Yingxi Li, Yifei Wang +1Compositional Reasoning RL Post-Training
Stanford University · Amazon AGI Labs
ExTra: Exploratory Trajectory Optimization for Language Model Reinforcement Learning
Jun 23, 2026Wenyang Hu, Junxiang Jia, Zhen Shu +3RL for Language Models RL for Language Model Reasoning
1National University of Singapore · 2SAP

Jun 26, 2026J/K move · Enter open · S save

Tandem Reinforcement Learning with Verifiable Rewards

Difan Jiao, Raghav Singhal, Robert West, Ashton Anderson

University of Toronto · EPFL

Reinforcement Learning RL for Language Model Reasoning Reinforcement Learning with Verifiable Rewards

Open paper AskPDF arXiv

Reinforcement learning with verifiable rewards (RLVR) has significantly improved the reasoning capability of large language models, reaching expert or even superhuman performance in domains such as competition math. However, whether weaker agents and humans can actually harness this capability is far less certain, with RLVR documented to drift reasoning toward idiosyncratic patterns such as poor readability and language mixing. Tandem training is a recently introduced paradigm that targets this compatibility problem: a trained, stronger senior co-generates each rollout with a frozen, weaker junior, and the two are rewarded as a team, so the senior is pushed to reason in ways the junior can follow. Yet this paradigm has so far been demonstrated only in proof-of-concept settings, leaving open whether it scales to the long chains of thought of the modern RLVR pipeline. In this work, we propose Tandem Reinforcement Learning (TRL), which carries the tandem training paradigm into RLVR. In TRL, the senior and a frozen junior alternate stochastically to co-generate the reasoning, the resulting generation is rewarded, and the standard GRPO loss is applied to the senior. Training Qwen3-4B-Instruct on competition math, we find that TRL matches vanilla GRPO on solo reasoning capability while three properties emerge together from the same rollout structure: stronger handoff robustness with the junior, reduced distributional drift from the junior, and a chain-of-thought more legible to the junior. Our results demonstrate a promising route for RLVR with practical payoffs in multi-model communication and human compatibility.

Abstract

Reinforcement Learning

Explore similar work

Tandem Reinforcement Learning with Verifiable Rewards

Compositional Reasoning in Language Models under Reinforcement Learning Post-Training

ExTra: Exploratory Trajectory Optimization for Language Model Reinforcement Learning