Rewarding Beliefs, Not Actions: Consistency-Guided Credit Assignment for Long-Horizon Agents

Problem
This paper addresses the limitations of reinforcement learning from verifiable rewards (RLVR) in partially observable environments, particularly in the context of long-horizon interactive tasks. The authors highlight that incomplete observations lead to drift in agent beliefs, while delayed rewards complicate the temporal credit assignment problem. This work is presented as a preprint and has not yet undergone peer review.

Method
The authors propose ReBel (Reward Belief), a novel reinforcement learning algorithm that explicitly models structured belief states to summarize an agent’s interaction history. The core technical contributions include:

1. Belief-Consistency Supervision: This mechanism converts discrepancies between predicted beliefs and observed feedback into dense self-supervised signals, eliminating the need for external step-wise annotations or verifiers.

2. Belief-Aware Grouping: This technique allows for the comparison of trajectories that share similar belief states, which enhances the robustness and reduces the variance of advantage estimates.

The architecture of ReBel is designed to integrate these components into the learning process, enabling agents to better navigate the complexities of long-horizon tasks. The training compute details are not disclosed, but the focus on belief states suggests a potentially increased computational overhead due to the additional modeling requirements.

Results
ReBel was evaluated on challenging long-horizon benchmarks, specifically ALFWorld and WebShop. The results indicate a significant improvement in task success rates, achieving up to a 20.4 percentage point increase over the episode-level baseline method, GRPO. Additionally, ReBel demonstrated a 2.1x increase in sample efficiency compared to GRPO. These results underscore the effectiveness of belief-aware self-supervision in enhancing decision-making capabilities in environments characterized by partial observability.

Limitations
The authors acknowledge that the reliance on structured belief states may introduce complexity in environments with highly variable dynamics or where belief states are difficult to define. They do not discuss potential scalability issues or the computational cost associated with the belief modeling, which could limit the applicability of ReBel in real-time systems. Furthermore, the performance gains are evaluated only on specific benchmarks, which may not generalize to all long-horizon tasks.

Why it matters
The implications of this work are significant for the development of more reliable long-horizon decision-making agents in partially observable environments. By focusing on belief states rather than actions, ReBel offers a new paradigm for credit assignment that could enhance the performance of large language model (LLM) agents in interactive tasks. This approach may pave the way for future research into belief-based reinforcement learning strategies, potentially leading to more robust and efficient agents capable of handling complex, real-world scenarios.

Authors: Wenjie Tang, Minne Li, Sijie Huang, Liquan Xiao, Yuan Zhou
Source: arXiv:2605.20061
URL: https://arxiv.org/abs/2605.20061v1