mlsanityData to 14 Oct 2026

Tropical Reinforcement Learning

arXiv 2610.02478 ↗First posted 1 Oct 2026cs.AIcited by 0

On the map: Deep reinforcement learning methods → RL training of language and agent models also fits: Interpretable and logic-guided RL

Abstract (arXiv)

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

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL training of language and agent models, one of 15 directions in Deep reinforcement learning methods. Builds on 35 of its 43 references that are in the map. First posted on arXiv 1 Oct 2026.

Builds on

35 of 43 references.

References · 35

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  3. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  4. 2023Let's Verify Step by Stepcited by 3,789
  5. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,211
  6. 2024HybridFlow: A Flexible and Efficient RLHF Frameworkcited by 2,057
  7. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 2,026
  8. 2022WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agentscited by 1,251
  9. 2025Kimi k1.5: Scaling Reinforcement Learning with LLMscited by 1,210
  10. 2022Measuring and Narrowing the Compositionality Gap in Language Modelscited by 1,075
  11. 2026DeepSeek-V4: Towards Highly Efficient Million-Token Context Intelligencecited by 1,040
  12. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 991
23 more
  1. 2025Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?cited by 982
  2. 2022Solving math word problems with process- and outcome-based feedbackcited by 901
  3. 2025Group-in-Group Policy Optimization for LLM Agent Trainingcited by 497
  4. 2025The Entropy Mechanism of Reinforcement Learning for Reasoning Language Modelscited by 485
  5. 2024ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Searchcited by 344
  6. 2025Reinforcement Learning with Verifiable Rewards Implicitly Incentivizes Correct Reasoning in Base LLMscited by 289
  7. 2019Measuring Compositional Generalization: A Comprehensive Method on Realistic Datacited by 284
  8. 2024VinePPO: Refining Credit Assignment in RL Training of LLMscited by 183
  9. 2017Imagination-Augmented Agents for Deep Reinforcement Learningcited by 140
  10. 2025Pass@K Policy Optimization: Solving Harder Reinforcement Learning Problemscited by 87
  11. 2025Optimizing Language Models for Inference Time Objectives using Reinforcement Learningcited by 53
  12. 2025From f(x) and g(x) to f(g(x)): LLMs Learn New Skills in RL by Composing Old Onescited by 42
  13. 2026Maximum Likelihood Reinforcement Learningcited by 36
  14. 2025Revisiting Entropy in Reinforcement Learning for Large Reasoning Modelscited by 21
  15. 2026RAGEN-2: Reasoning Collapse in Agentic RLcited by 20
  16. 2026Save the Good Prefix: Precise Error Penalization via Process-Supervised RL to Enhance LLM Reasoningcited by 11
  17. 2025Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Gamecited by 9
  18. 2026Reason in Chains, Learn in Trees: Self-Rectification and Grafting for Multi-turn Agent Policy Optimizationcited by 8
  19. 2026From Reasoning Traces to Reusable Modules: Understanding Compositional Generalization in Language Model Reasoningcited by 5
  20. 2026Credit Assignment with Resets in Language Model Reasoningcited by 4
  21. 2026Reinforcement Learning for Compositional Generalization with Outcome-Level Optimizationcited by 2
  22. 2026RL Post-Training Builds Compositional Reasoning Strategiescited by 2
  23. 2019Max-Plus Matching Pursuit for Deterministic Markov Decision Processescited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026From Reasoning to Agentic: Credit Assignment in Reinforcement Learning for Large Language Models
  2. 2026A Relative-Budget Theory for Reinforcement Learning with Verifiable Rewards in Large Language Model Reasoning
  3. 2026Re2: Unlocking LLM Reasoning via Reinforcement Learning with Re-solving
  4. 2025Compositional Instruction Following with Language Models and Reinforcement Learning
  5. 2022lilGym: Natural Language Visual Reasoning with Reinforcement Learning
  6. 2025RLVE: Scaling Up Reinforcement Learning for Language Models with Adaptive Verifiable Environments
  7. 2020Learning to Generalize for Sequential Decision Making
  8. 2025d-TreeRPO: Towards More Reliable Policy Optimization for Diffusion Language Models