acceptodds
Under review as a conference paper at ICLR 2027

Rewarding Beliefs, Not Only Actions: Belief-Consistent Reinforcement Learning for Long-Horizon Agents

Abstract

Reinforcement learning from verifiable rewards (RLVR) is a promising paradigm for improving large language model (LLM) agents on long-horizon interactive tasks. However, in partially observable environments, incomplete observations cause agent beliefs to drift over time, while delayed rewards obscure the causal impact of intermediate decisions, exacerbating temporal credit assignment challenges. To address this, we propose ReBel (Reward Belief), a process-level reinforcement learning algorithm that explicitly models structured belief states to summarize interaction history and guide subsequent policy learning. ReBel introduces belief-consistency supervision, converting discrepancies between predicted beliefs and observed feedback into dense self-supervised signals without requiring external step-wise annotations or verifiers. It also employs belief-aware grouping to compare trajectories under similar belief states, yielding more robust and lower-variance advantage estimates. We evaluate ReBel on challenging long-horizon benchmarks, including ALFWorld and WebShop. ReBel improves task success by up to percentage points over the episode-level baseline GRPO and increases sample efficiency by . These results suggest that belief-aware self-supervision is a promising direction for reliable long-horizon decision-making under partial observability.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM Agents,Agentic RL,Credit Assignment

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_H1nvOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes an RL framework for LLM agents in the partially observable environment to address the belief drift and insufficient process rewards. The main idea of the proposed method includes explicit belief tracking, belief-consistency reward design, and belief-based advantage estimation.Experiments on ALFWorld and WebShop shows gains over episode-level GRPO and step-level GiGPO using Qwen2.5-1.5B-Instruct.

Critical strengths

Using model's own belief and environment's feedback to supervise intermediate state understanding is a sample-efficient and less costly way to provide process rewards for on-policy RL.

Critical weaknesses
  1. The central belief-based step grouping is insufficiently specified and differs across descriptions. Section 3.3 defines groups through equality of belief predicates, whereas Appendix A.3 states that ALFWorld actually uses an environment-derived task-phase anchor augmented with unspecified structural flags. The paper does not explain how these anchors and flags are computed or reconcile the two formulations. It is crucial to determine precisely what makes steps comparable in order to assess whether the benefit comes from belief modeling rather than simpler task-progress grouping.
  2. Insufficient baselines and experiments:
  • There are many step-level methods [1-3] but the paper only compares with GiGPO (not a recent baseline).
  • ALFWorld and WebShop are too old and simple benchmarks for recent LLMs, where the state and action space are finite and closed. Other tasks like agentic coding[4,5] or complex gaming (e.g, Minecraft/Pokemon) are expected to evaluate the method, especially open-ended state-action spaces that LLMs are better to handle compared to traditional ML models.
  • The closed-source frontier models are out-dated as baselines, and more recent LLMs (e.g., GPT-6/Gemini-3.8/Opus-5) should be compared.
  • Only Qwen2.5-1.5B-Instruct as the backbone. A larger and more backbones (e.g.,qwen-3.8-27b) should be added to show the method's robustness across models.

References:

  1. Zhang, Zijing, et al. "Rlvmr: Reinforcement learning with verifiable meta-reasoning rewards for robust long-horizon agents." ICLR, 2026.
  2. Liu, Xiaoqian, et al. "Agentic reinforcement learning with implicit step rewards." ICLR, 2026.
  3. Zou, Jiaru, et al. "Reasonflux-prm: Trajectory-aware prms for long chain-of-thought reasoning in llms." Advances in Neural Information Processing Systems 38 (2026): 26764-26802.
  4. https://openai.com/index/introducing-swe-bench-verified/
  5. Trivedi, Harsh, et al. "Appworld: A controllable world of apps and people for benchmarking interactive coding agents." Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.
Questions for authors
  1. What exact inputs and rules produce the belief anchors used in the experiments, including task phases, structural flags, and canonicalization, and how does this implementation correspond to the predicate-equality grouping defined in Section 3.3?
  2. How are consistency checks implemented when an action changes a predicate’s truth value, how does delayed verification distinguish an initially incorrect belief from a subsequent state change, and what value of the consistency-reward weight η\eta was used?
  3. Are SFT initialization, training data, clipping, entropy protection, rollout budgets, and evaluation protocols held fixed across B1–B3, particularly between B2 and B3?
  4. What evidence supports the claim that ReBel reduces belief drift?
Reviewer_smhFOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

ReBel trains LLM agents (Qwen2.5-1.5B) on ALFWorld and WebShop. At each step the agent outputs a structured <belief> (predicates over object locations, states and task phase), then <think>, then <action>. The method has two components:

  1. Belief-consistency reward. At each step, rtconsr^{\text{cons}}_t is the fraction of the belief's checkable predicates that agree with the next observation. A pending buffer assigns credit later for predicates that only become verifiable after a delay. The predicate vocabulary and verification rules are generated by an LLM.
  2. Belief-anchor advantage. A step-level advantage is normalized within groups of steps that share the same belief anchor, and added to the GRPO episode advantage with weight ω=0.5\omega=0.5.

Before RL, ReBel is SFT-initialized on 426 ALFWorld and 500 WebShop expert trajectories whose beliefs were annotated by GPT-5.4. Reported results are 93.2% on ALFWorld and 75.1% SR on WebShop: +20.4 / +18.3 points over GRPO and +6.5 / +7.7 over GiGPO. The paper also reports a 2.1× sample-efficiency gain, an incremental ablation (B0–B3), and belief-quality diagnostics.

Critical strengths
  1. A reasonable and practical idea. Making the agent state explicit lets the environment check it. This turns observations into dense, verifier-free feedback on state tracking, and it is a sensible direction for partially observable agentic RL. The pending buffer for delayed verifiability is a thoughtful detail.
  2. Candid diagnostics. The appendix states its own limits honestly. Appendix C.2 acknowledges that the diagnostic run differs in clipping and entropy settings, and that seed variance undercuts the belief-correction claim. Case study D.2 shows a residual "post-placement regression" failure mode. Appendix E.3 declines to claim variance reduction.
Critical weaknesses

W1. The main comparison is not controlled.

  • Baselines appear transcribed. The RL baselines in Table 1 (PPO 54.4, RLOO 69.7, GRPO 72.8, GiGPO 86.7 / 86.1) and the prompt baselines appear to match the numbers reported in Feng et al. (2025). If so, they were not rerun in the authors' stack.
  • Different starting points. ReBel alone starts from an SFT model trained on GPT-5.4-annotated expert trajectories; the baselines start from the base instruct model. The 2.1× "sample-efficiency" claim (Fig. 2a, 3c) compares a warm-started model with cold-started baselines, so it largely measures the SFT warm start.
  • Different optimizer settings. Appendix C.2 reveals that ReBel uses asymmetric clipping (0.2/0.28) with entropy protection, while the GRPO-Belief run uses 0.2/0.2 without it. Clip-higher alone is known to matter in agentic RL.
  • Inconsistent training budgets. Appendix A.1 says ReBel trains for 100 iterations and baselines for 150, yet also claims "methods share an identical training budget."
  • Numbers that don't reconcile. The ablation's B0 GRPO scores 60.9 vs 72.8 in Table 1, and the full method scores 96.9 vs 93.2. It is unclear whether B0–B3 share the belief-SFT initialization.
  • A puzzling SFT result. "SFT only" scores 3.6% after training on 426 expert trajectories, which is hard to reconcile with standard results.

Taken together, no reported number isolates the effect of the belief reward or the belief grouping against an equally initialized, equally configured baseline.

W2. The described method is not the implemented method, and the consistency reward can be gamed.

Grouping. Section 3.3 motivates grouping by the agent's own belief predicates. Appendix A.3 states that in the ALFWorld experiments the grouping key is "the environment-derived phase anchor, augmented with structural flags taken from the belief (rather than the raw predicate tuple)."

  • This is a hand-designed, environment-side state abstraction, close in spirit to GiGPO's anchor-state grouping but coarser.
  • The singleton-ratio comparison with GiGPO (Fig. 3a) is therefore largely by construction.
  • Phase-level groups also mix very different states, which the paper itself notes can destroy contrast (E.3).

Step return. The definition is inconsistent:

  • Section 3.3: the full-horizon discounted renv+ηrconsr^{\text{env}}+\eta r^{\text{cons}}, with η\eta unreported.
  • Appendix E: a short-horizon sum of rconsr^{\text{cons}} only.

Reward incentives. rconsr^{\text{cons}} is a masked precision over predicates the policy itself chooses to assert. This creates several incentives:

  • The policy can raise the reward by asserting fewer predicates, asserting only safe ones, or restating what it has just observed. Nothing rewards recall or genuine prediction.
  • The prediction field, which is the part that would test forward modeling, appears not to be scored. In the case studies the predictions are routinely hallucinated (e.g. invented countertop contents) without visible consequence.
  • Comparing btb_t against ot+1o_{t+1} after action ata_t penalizes beliefs that were correct before the action changed the state, e.g. "mug on countertop" just before "take mug."

The verifier. The claim of needing no "external verifiers" is overstated. The LLM-generated, environment-specific verification rules are a step-wise verifier, and how CkC_k is computed from text observations is not specified.

Questions for authors
  1. Were the baselines in Table 1 rerun, or taken from Feng et al. (2025)? Please report GRPO and GiGPO trained from the same belief-SFT checkpoint, with the same clipping, entropy and iteration budget as ReBel. This is the decisive experiment.
  2. What exactly is the grouping key used for each benchmark? Please report the ablation of (a) agent-belief-predicate grouping vs (b) environment phase grouping vs (c) GiGPO anchor grouping, all under identical initialization.
  3. Which step return is used in training (Section 3.3 or Appendix E), and what is η\eta? Is the prediction field scored?
  4. How does the number of asserted predicates per step evolve during training? A decreasing count with rising rconsr^{\text{cons}} would indicate reward hacking.
  5. Please reconcile B0 (60.9) and B3 (96.9) with Table 1 (72.8 / 93.2). What explains SFT-only at 3.6%?
  6. (Clarification.) How is CkC_k computed from text observations, and how accurate is it against simulator ground truth?
Reviewer_1XYMOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes ReBel, a belief-consistent reinforcement learning framework for long-horizon LLM agents operating in partially observable environments. The method introduces an explicit Belief-Think-Action generation structure to maintain task-relevant state information throughout interaction. It further develops belief-consistency rewards that evaluate generated beliefs against subsequent environmental observations, providing dense process-level supervision without manually annotated step-wise rewards. Additionally, belief-anchor grouping enables step-wise advantage estimation by comparing decisions associated with similar belief representations. Experiments on ALFWorld and WebShop demonstrate improvements over GRPO and GiGPO using Qwen2.5-1.5B-Instruct. ReBel achieves success rates of 93.2% and 75.1%, respectively, and reports improved sample efficiency. The paper also includes component ablations, grouping analyses, and belief-quality diagnostics.

Critical strengths
  1. Meaningful motivation and belief-aware process supervision. The paper identifies belief drift and sparse-reward credit assignment as important challenges in long-horizon agentic RL. Explicitly separating belief formation, reasoning, and action selection provides an interpretable framework for analyzing intermediate decisions. The belief-consistency reward and belief-anchor grouping offer a reasonable approach to exploiting environmental feedback for more fine-grained policy optimization.

  2. Promising empirical improvements and supporting analyses. ReBel achieves substantial success-rate improvements over GRPO and GiGPO on both ALFWorld and WebShop. The results are reported across three training seeds, and the paper provides incremental ablations, training-efficiency comparisons, and belief-quality diagnostics. These analyses offer useful evidence that structured belief representations and step-level optimization can benefit long-horizon decision-making.

Critical weaknesses
  1. Insufficient clarification of belief verification and grouping reliability. The belief-consistency reward compares the belief at step (t) with observations obtained after executing the action. However, actions may legitimately change the environment state, raising the question of how the verification mechanism distinguishes an incorrect prior belief from a correct belief invalidated by the action itself. Furthermore, the formal binary predicate representation does not clearly explain how unknown or unresolved states are handled in practice. For belief-anchor grouping, Appendix A.3 describes using environment-derived task-phase anchors augmented with structural flags, rather than the exact belief-predicate equivalence presented in Section 3.3. This discrepancy deserves clarification, particularly because grouping semantically similar but decision-relevant distinct states could introduce biased advantage estimates. Although the paper reports lower singleton ratios, this alone does not establish more accurate or lower-variance credit assignment.

  2. Potential confounding factors in experimental comparisons and ablations. ReBel uses an additional belief-annotated SFT initialization constructed from expert trajectories, but it is insufficiently clear whether all RL baselines receive equivalent initialization and structured prompting. The ablation study also combines grouping and step-wise advantages in a single configuration, making their individual contributions difficult to isolate. Moreover, Table 1 reports 93.2% for ReBel and 72.8% for GRPO on ALFWorld, whereas Table 2 reports 96.9% and 60.9%, respectively, without sufficiently explaining the differences in experimental settings or statistical aggregation. Appendix A additionally indicates different training iteration budgets for ReBel and the RL baselines. These issues make it difficult to determine how much of the performance improvement can be attributed specifically to belief-consistency supervision and belief-aware advantage estimation.

  3. Limited generalization and incomplete efficiency validation. The evaluation is restricted to two text-based, relatively controlled interactive environments. Although the predicate-construction pipeline is described as automatic, it relies on an expert LLM to generate environment-specific predicates and verification rules, leaving its reliability and transferability to more complex environments uncertain. The claimed sample-efficiency improvements are also not accompanied by comprehensive comparisons of total training time, token consumption, or preprocessing overhead. Additionally, Appendix C.2 acknowledges substantial variation in belief-correction behavior across seeds, while the principal belief-quality diagnostics rely on a selected checkpoint. Finally, although ReBel improves WebShop success rate, its average task score (79.8) remains below the strongest GiGPO variant (83.5), suggesting that the improvements are not uniform across evaluation metrics.

Questions for authors
  1. Fairness of Baseline Comparisons and Ablations. Could the authors clarify whether GRPO and GiGPO receive the same belief-annotated SFT initialization, prompt format, and optimization settings as ReBel? A comparison using identical initialization and training budgets would better isolate the benefits of the proposed method. Additionally, could the authors explain the differences between the ALFWorld results in Tables 1 and 2 and provide separate ablations for belief grouping and step-wise advantage estimation?

  2. Belief Verification and Reward Reliability. How does the consistency verifier distinguish an erroneous belief from a previously correct belief that becomes outdated because of an executed action? How are unknown, unverified, and temporarily unobservable predicates represented and handled in reward computation? Since the reward depends on the predicates being checked, could the authors also explain how the method prevents the agent from improving consistency scores simply by making fewer verifiable assertions?

  3. Belief-Anchor Grouping and Credit Assignment. Section 3.3 defines groups using equivalent belief states, whereas Appendix A.3 describes environment-derived phase anchors with additional structural flags. Could the authors clarify the exact grouping implementation and whether it relies exclusively on policy-generated information? More importantly, could they compare alternative grouping strategies and report within-group return variance or advantage-estimation stability? This would help establish whether the performance gains arise from improved state abstraction rather than merely larger comparison groups.

  4. Generalization, Efficiency, and Robustness. How well would ReBel transfer to environments with stochastic transitions, ambiguous feedback, or predicates that cannot be reliably verified? Could the authors provide a breakdown of total computational costs, including belief generation, expert-LLM-based predicate construction, and RL training? Finally, given the seed-dependent behavior acknowledged in Appendix C.2, could the authors provide aggregate belief-quality diagnostics across all training seeds to better substantiate the claimed reduction in belief drift?

If the aforementioned concerns are satisfactorily addressed, particularly the fairness of the experimental comparisons and the reliability of belief-based credit assignment, I would consider raising my rating.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.