FESGPO: Free-Energy and Structure-Aware Credit Assignment for Multi-Turn Agents

Reinforcement Learning (RL) for multi-turn Large Language Model (LLM) agents often needs to identify which intermediate decisions actually drive task completion from sparse terminal feedback. Existing group-based methods do not fully exploit the probabilities and costs of successful paths across rollouts or the decision structure within trajectories. To bridge this gap, we propose FESGPO, which treats the rollout group of a given task as a finite observation of the policy–environment interaction process. In this view, transition frequency and path length capture the reliability and cost of an action's route to success. From these statistics, FESGPO estimates empirical transition probabilities and aggregates all successful paths in the empirical graph into a statistical-physics free energy. The corresponding Bellman recursion decomposes this free energy into the shortest success distance, the empirical success probability, and the excess path cost. Furthermore, exact repeated transitions, temporal order, and the final outcome enable more precise attribution of terminal credit to specific decisions. FESGPO exploits this structure to redistribute terminal credit, concentrating the training signal on decisions that materially shape subsequent behavior. At Qwen2.5-1.5B, FESGPO improves strict success over the strongest trained baselines by 7.29 percentage points on ALFWorld and 2.87 percentage points on WebShop. It raises nonzero PPO-advantage coverage from 24.07% to 56.68% and surpasses GraphGPO with dynamic sampling on ALFWorld using 16.15% as many rollouts. We verify our main theoretical results in Lean 4. Our implementation is available at https://anonymous.4open.science/r/FESGPO.