Tropical reinforcement learning improves language model reasoning ability
Tropical Reinforcement Learning
Artificial Intelligence
Summary
Traditional reinforcement learning adds up the chances of all correct answers but can’t tell which exact answer worked best and sometimes forgets good partial solutions. The authors propose Tropical Reinforcement Learning, which changes the math to choose the best solution instead of summing all of them. This lets the model combine different successful reasoning steps from separate tries, improving its ability to solve complex problems step-by-step. They built an algorithm called TROPIC and tested it on several tasks, where it beat previous methods by a significant margin.
What this means in practice
- •For game ai developers: Use tropical reinforcement learning to improve agent decision-making in puzzle and grid-based games by combining partial successful strategies.
- •For robotics control teams: Improve composition of control sequences in resettable robotic tasks by reinforcing best partial solutions found in different trials.
Authors
Arip Asadulaev, Aladin Djuhera, Karim Salta, Holger Boche, Fakhri Karray, Martin Takac
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