Selective Successor Eligibility Traces for RLVR
TL;DR
This work proposes Selective Successor Eligibility Traces (S-trace), an critic-free eligibility trace method that enables more effective credit assignment and establishes an upper bound on its discrepancy from the raw eligibility traces-based policy gradient estimator.
Abstract
Reinforcement Learning with Verifiable Rewards (RLVR) has become a key approach for improving the reasoning abilities of large language models. However, widely used critic-free algorithms such as Group Relative Policy Optimization (GRPO) suffer from coarse-grained temporal credit assignment, as they assign the same trajectory-level advantage to all tokens and fail to distinguish the contributions of different reasoning steps. To address this challenge, we propose Selective Successor Eligibility Traces (S-trace), an critic-free eligibility trace method that enables more effective credit assignment. S-trace introduces successor importance reweighting to recover downstream credit signals under PPO-style clipping and propagates them to selected historical tokens through entropy-based token selection. Theoretically, we establish an upper bound on its discrepancy from the raw eligibility traces-based policy gradient estimator, jointly controlled by the KL divergence and the trace decay factor $\lambda$. Experiments show that S-trace achieves absolute gains in average pass@16 of 1.80\% and 6.17\% over GRPO, and 2.32\% and 0.87\% over trace-style GRPO($\lambda$), on Qwen3-1.7B and Qwen3-4B, respectively, while maintaining robust gains on Qwen3-8B and producing shorter responses.
