Intrinsic Credit Assignment for Long Horizon Interaction

How can we train agents to navigate uncertainty over long horizons? In this work, we propose ∆Belief-RL, which leverages a language model's own intrinsic beliefs to reward intermediate progress. Our method utilizes the change in the probability an agent assigns to the target solution for credit assignment. By training on synthetic interaction data, ∆Belief-RL teaches information-seeking capabilities that consistently outperform purely outcome-based rewards for RL, with improvements generalizing to out-of-distribution applications ranging from customer service to personalization. Notably, the performance continues to improve as we scale test-time interactions beyond the training horizon, with interaction-efficiency increasing even on Pass@k metrics. Overall, our work introduces a scalable training strategy for navigating uncertainty over a long-horizon, by enabling credit assignment to intermediate actions via intrinsic ∆Belief rewards.

When an AI assistant has to figure something out through a back-and-forth conversation, like narrowing down a product fault, learning your preferences, or playing a guessing game, it often takes many turns to reach the answer. The hard part of training such systems is that they usually only learn whether they succeeded at the very end. They get no feedback on whether each question along the way was actually helpful, which makes learning slow. We found that a language model already carries an internal hunch about the right answer, and we can read off how confident it is at each step. Our method, ΔBelief-RL, rewards the AI whenever a question nudges this confidence toward the correct answer, giving feedback after every turn instead of only at the end. Agents trained this way learn faster and ask fewer redundant questions. Remarkably, our small models outperform general-purpose systems that are many times larger, and the skill transfers to unseen tasks like customer service. This points toward AI that reasons about its own progress, much as people do.