LLM agents acting over long horizons in partially observable environments face two problems: they need to track uncertainty about unobserved world attributes, and their context grows unbounded, diluting task-relevant information. The authors propose Agent-BRACE, which decouples the agent into a belief state model (producing a set of natural language claims about the environment, each tagged with a certainty label from "certain" to "unknown") and a policy model that acts based on this compact belief, not the full history. Both are jointly trained via RL. Across embodied language environments, Agent-BRACE improves average performance by +14.5% (3B) and +5.3% (4B) over strong RL baselines while keeping context size constant regardless of episode length.
Main takeaways:
- Long-horizon, partially observable tasks require tracking uncertainty and managing growing context
- Agent-BRACE separates belief tracking (atomic claims + certainty labels) from action selection (policy conditioned on belief)
- Belief state is structured natural language: claims like "the key is in room A" tagged with "likely" or "unknown"
- Achieves +14.5% (3B) and +5.3% (4B) improvement on average, with near-constant context size
- Reduces premature termination and hallucinations by distributing cognition across structured reasoning threads