Technische Samenvatting: Versterken van Multi-Turn Redeneren in LLM-agenten via Fijnmazige Beloningsstructuren en Credit Assignment

1. Probleemstelling

Reinforcement Learning (RL) is een primaire mechanisme geworden voor het verbeteren van de redeneervermogens van Large Language Models (LLMs) in complexe, langdurige, multi-turn scenario's. Deze interacties worden formeel gemodelleerd als turn-level Markov Decision Processes (MDPs). Een kritieke beperking in de bestaande literatuur is echter de afhankelijkheid van ijle (sparse) traject-niveau beloningen (bijv. alleen de correctheid van het uiteindelijke antwoord). Deze aanpak leidt tot slechte credit assignment, waarbij het model moeite heeft om succes of falen toe te schrijven aan specifieke tussenliggende stappen (turns) binnen een multi-turn traject.

Hoewel sommige eerdere werken proberen om tussenliggende signalen op te nemen, voegen zij vaak outcome- en tussenliggende beloningen samen in één vertraagde traject-niveau signaal, waardoor ze niet de fijnmazige supervisie bieden die nodig is voor effectief leren in dynamische omgevingen. Bijgevolg hebben agenten moeite met het verfijnen van gedragingen zoals query-selectie in zoektaken of strategische zetten in spellen, omdat ze geen dichte feedback missen op het niveau van individuele interactie-turns.

2. Methodologie

Het paper stelt een systematische investigatie voor naar het benutten van dichte turn-level beloningsstructuren om fijnmazige credit assignment mogelijk te maken. De auteurs categoriseren beloningsstructuren in drie verschillende typen op basis van granulariteit, elk corresponderend met een specifieke turn-level MDP-formulering:

1. Terminale Beloning ($M_1$): Biedt alleen een uiteindelijke outcome-beloning (bijv. de correctheid van het antwoord) zonder tussenliggende signalen.
2. Vertraagde Beloning ($M_2$): Voegt tussenliggende en outcome-beloningen samen in één vertraagd signaal dat aan het einde van het traject wordt toegewezen.
3. Per-Turn Beloning ($M_3$): Biedt expliciete, dichte beloningen bij elke turn, waarbij de correctheid van individuele agent-omgeving interacties (bijv. tool-aanroepen en resultaten) wordt geëvalueerd.

De auteurs leiden op maat gemaakte RL-algoritmen af voor Group Relative Policy Optimization (GRPO) en Proximal Policy Optimization (PPO) om deze verschillende MDP-formuleringen te accommoderen.

2.1. GRPO met Fijnmazige Credit Assignment (MT-GRPO)

Standaard GRPO berekent advantages op traject-niveau, waarbij een uniforme advantage wordt toegewezen aan alle tokens in een respons. Om dit aan te pakken, introduceren de auteurs Multi-Turn GRPO (MT-GRPO):

• Advantage Decompositie: De methode definieert twee soorten advantages:
  • Outcome Advantage ($A^O$): Legt globale taakvoltooiingssignalen vast op basis van het uiteindelijke antwoord.
  • Intermediate Advantage ($A^I$): Legt lokale optimalisatiesignalen vast door returns over trajecten op hetzelfde tijdstip (turn) te vergelijken.
• Geaggregeerde Advantage: Deze worden gecombineerd in een unificerende advantage-functie die credit toewijst op zowel globale als lokale schaal door huidige en toekomstige advantages te aggregeren:
  $$A^{MT-GRPO}_{i,(k)} = \sum_{l=k}^{K-1} \alpha^{l-k} A^I_{i,(l)} + \alpha^{K-k} A^O_i$$
  waarbij $\alpha$ een discount-coëfficiënt is.
• Rollout Structuur: In tegenstelling tot standaard GRPO dat per-traject rollouts uitvoert, voert MT-GRPO per-state (per-turn) rollouts uit. Dit resulteert in een boom-gebaseerde structuur waarbij $G$ samples worden genomen bij elke turn, wat leidt tot $G^{K-1}$ totale trajecten voor een horizon van $K$ turns.

2.2. PPO met Turn-Level Beloningen (MT-PPO)

Voor PPO maken de auteurs gebruik van Generalized Advantage Estimation (GAE) om turn-level beloningen te incorporeren:

• Beloningsassignatie: In de MT-PPO variant worden tussenliggende beloningen toegewezen aan de laatste token van de corresponderende turn, terwijl de outcome-beloning wordt toegewezen aan de laatste token van het gehele traject.
• TD Error Modificatie: De Temporal-Difference (TD) error $\delta_t$ wordt aangepast om expliciete per-turn beloningen ($R_I$) bij turn-grenzen te incorporeren, waardoor de value function fijnmazige trainingssignalen kan bieden bij elke stap.
• Turn-Gedecodeerde PPO: Het paper onderzoekt ook een variant waarbij multi-turn rollouts worden gedecomposeerd in single-turn trainingsinstanties. Echter, experimenten suggereren dat deze eenvoudige decompositie kan leiden tot suboptimale credit assignment als deze niet zorgvuldig is afgestemd op het uiteindelijke taaksucces.

3. Belangrijkste Bijdragen

1. Taxonomie van Beloningsstructuren: Het paper categoriseert multi-turn RL formeel in drie MDP-formuleringen ($M_1, M_2, M_3$) op basis van beloningsgranulariteit en leidt specifieke GRPO- en PPO-algoritmen af voor elk.
2. MT-GRPO Algoritme: Een nieuwe GRPO-variant die per-turn rollouts en geaggregeerde advantages gebruikt om credit assignment op zowel globale als lokale schaal mogelijk te maken.
3. MT-PPO Strategie: Een verfijnde beloningsassignatie-strategie binnen GAE voor PPO die expliciet dichte per-turn beloningen gebruikt, wat een superieure stabiliteit en convergentie demonstreert ten opzien van traject-niveau baselines.
4. Empirische Validatie: Uitgebreide experimenten op multi-turn zoekagenten (met behulp van Wikipedia search) en game-agenten (Sokoban) tonen aan dat dichte per-turn beloningsstructuren consequent beter presteren dan ijle terminale en vertraagde beloningsstructuren.

4. Experimentele Resultaten

De auteurs evalueerden hun methoden op twee primaire domeinen: Multi-Turn Search Agents en Multi-Turn Game Agents.

4.1. Search Agents (Vraagbeantwoording)

• Datasets: NQ, TriviaQA, PopQA (General QA); HotpotQA, 2WikiMultiHopQA, Musique, Bamboogle (Multi-Hop QA).
• Setup: Gebruikte Qwen2.5-7B als het basismodel en een LLM-gebaseerde judge (GPT-OSS-120B) om tussenliggende turn-level beloningen te leveren.
• Bevindingen:
  • Trainingsdynamiek: MT-PPO vertoonde aanzienlijk grotere trainingsstabiliteit en snellere convergentie vergeleken met PPO-OR (alleen terminaal) en PPO-MR (vertraagd). PPO-OR en PPO-MR vertoonden hoge variantie en prestatie-degradatie, met name op complexe multi-hop datasets.
  • Prestaties: MT-PPO behaalde de hoogste antwoordcorrectheid (Exact Match) over alle datasets, waarbij het state-of-the-art methoden (inclusclusief StepSearch en PPR) met significante marges versloeg (bijv. +3,5% over PPO-OR gemiddeld).
  • Formaat en Retrieval: MT-PPO behaalde bijna perfecte format-correctheid (~100%) en een meer consistente retrieval-accuratesse, wat aangeeft dat turn-level beloningen structurele restricties effectief afdwingen en redenering sturen.

4.2. Game Agents (Sokoban)

• Setup: Gebruikte Qwen2.5-VL-3B in een 6x6 grid Sokoban-omgeving, een taak die irreversibele, langdurige planning vereist.
• Bevindingen:
  • MT-PPO behaalde de hoogste Success Rate (0.6563) en Effective Action Rate (0.9870) bij stap 300, waarmee het GRPO en PPO baselines significant versloeg.
  • De methode demonstreerde het vermogen om stabiele, doelgerichte actiesequenties te leren, waarbij het effectief omgaat met de irreversibele aard van de omgeving waar één verkeerde zet leidt tot een doodlopend pad.

4.3. GRPO Resultaten

In de twee-turn search setting presteerde MT-GRPO beter dan GRPO-OR en GRPO-MR op alle beloningsmetrieken, inclusief tool-executie, search answer correctness en exact match accuratesse. Opvallend genoeg vertoonde MT-GRPO een lagere variantie tijdens de training en het vermogen om te herstellen van tijdelijke dalingen in tool-gebruik, wat de robuustheid van fijnmazige credit assignment benadrukt.

5. Betekenis en Claims

Het paper claimt dat dichte turn-level beloningsstructuren en fijnmazige credit assignment fundamenteel zijn voor het verbeteren van de prestaties van LLM-agenten in langdurige, multi-turn taken.

• Superioriteit boven IJle Beloningen: De auteurs stellen dat voor zowel GRPO als PPO, dichte per-turn beloningsstructuren consequent beter presteren dan ijle terminale en vertraagde beloningsontwerpen wat betreft trainingsdynamiek, convergentiesnelheid en uiteindelijke numerieke prestaties.
• Stabiliteit en Robuustheid: De voorgestelde methoden (MT-PPO en MT-GRPO) bieden grotere trainingsstabiliteit, waardoor de variantie en de instorting (collapse) die vaak worden waargenomen bij traject-niveau RL-benaderingen, worden verminderd.
• Generaliseerbaarheid: De aanpak blijkt effectief te zijn over diverse domeinen, van informatie retrieval (search) tot complexe besluitvorming (Sokoban), wat valideert dat expliciete turn-level feedback cruciaal is voor agenten om effectieve interactiestrategieën met dynamische omgevingen te leren.

Het paper concludeert dat het benutten van deze dichte beloningsstructuren het mogelijk maakt voor LLM-agenten om hun gedrag te verfijnen op het niveau van individuele interactiestappen, wat leidt tot nauwkeurigere uiteindelijke uitkomsten en beter gestructureerde outputs.