Cheap Retrieval and Observation Credit Assignment from One Quantity: The Value of Information

Daniel Strauss, Nikolaos Sotirakis, Zhenshan Bing, Alois KnollarXiv 2026 · arXiv

This paper, presented at the CoRL 2026 Workshop on Memory for Robot Foundation Models, proposes a unified solution to two of the biggest headaches in memory-based Reinforcement Learning (RL): how to find the right memory efficiently and how to reward the action that stored it in the first place. The authors argue that both problems can be solved by calculating a single quantity: the Value of Information (VoI).

TL;DR

The authors use a learned world model to estimate the "Value of Information" (VoI) of past observations. This single metric is used to both select the most relevant memories for a decision (reducing retrieval costs) and to provide a provable lower bound for credit assignment, ensuring that actions taken to acquire information are properly rewarded.

What Problem Does This Paper Address?

Memory is expensive for robots. Imagine a robot repairing an appliance: it sees a specific wire configuration at step 10, but doesn't need that information until step 500.

Current RL agents face two main hurdles here:

  1. Retrieval Cost: Standard attention mechanisms (like those in Transformers) have to "look" at every single past frame to find the relevant one. As the robot's history grows, this becomes computationally and energetically prohibitive.
  2. Observation Credit Assignment Problem (O-CAP): Standard RL algorithms struggle to link the reward at step 500 back to the "look" action at step 10. If the robot doesn't know why looking was useful, it might never learn to perform that information-gathering action again.

Methods

The core idea is to treat information as a commodity with a measurable value.

  • Defining VoI: Following classical decision theory, the authors define the Value of Information as the change in achievable return when a decision-maker gains access to a specific subset of recorded history.
  • World Model Estimation: To avoid needing separate trajectories for every possible "what if I didn't see that?" scenario, the authors train a world model on archived rollouts. By masking specific past observations in the model, they can estimate how much the expected return would drop without that information.
  • The Acquisition Bound: The paper mathematically proves that the VoI of an observation provides a lower bound (a "floor") for the Temporal Difference (TD) target of the action that acquired it. This allows for immediate credit assignment to informative actions, rather than waiting for reward signals to propagate back through hundreds of steps.
  • Memory Navigation (The "Memory Ghost"): For efficient retrieval, they introduce a pilot system where a persistent pointer—the Memory Ghost—moves through an external memory store. Instead of attending to everything, the agent only "sees" what the Ghost points to, making retrieval costs constant regardless of memory size.
Figure 1: Information value on a recorded POMDP trajectory. Decision t needs x1 (at s) and x2 (at u) jointly; the look at k−1 would repeat x1 but is not taken, so R = ∅attains the sup in Eq. (7). Bellman backups carry the reward back step by step; from t, where the information changes the action, the dual arrow jumps back. Along orange it credits the acquiring actions, flooring their TD targets; x1 is credited since x2 is in its base set. Along blue it values recalling s and u jointly.

Datasets

The authors evaluated their "Memory Navigation" pilot on:

  • MiniGrid-Memory-S9: Used for pretraining.
  • MiniGrid-Memory-S17Random: A more complex variant used for fine-tuning. These environments are standard benchmarks for testing an agent's ability to remember a cue seen early in an episode and use it much later.

Key Insights and Ideas

  • Unification: The realization that the same math used to decide what to remember can also be used to decide what to reward.
  • Synergy and Redundancy: The proposed VoI calculation (Equation 7) explicitly handles synergistic information (two observations that are only useful together) and redundant information (multiple observations of the same thing), ensuring credit is assigned fairly.
  • Faster Convergence: By "flooring" the TD target with the VoI, the authors hypothesize that agents will learn informative actions much faster than with standard backpropagation of rewards.

Key Results

In the MiniGrid-Memory-S17Random task:

  • Memory Navigation (the proposed retrieval system) reached a mean return of 0.95 in just 0.59M steps.
  • Absolute-position retrieval (a common baseline) took 0.94M steps to reach similar performance.
  • No retrieval head (standard Transformer-XL) took 1.38M steps.
  • The system achieved these results with a significantly reduced context (only 5 tokens), demonstrating that selective retrieval is highly effective.

Limitations and Future Work

  • Hypothesis Stage: While the retrieval system was tested, the full "floored target" for credit assignment (Equation 9) is currently a theoretical proof and has not yet been implemented in a training loop.
  • Estimation Bias: The authors note that taking a supremum over noisy world model estimates can lead to an upward bias, potentially pushing the estimated "floor" above the true optimal value ($Q^*$).
  • Causality: The current VoI metric doesn't distinguish between an observation being useful and it being causally necessary for the chosen action.
  • Future Directions: The authors suggest using the world model to identify which parts of a trajectory are most informative for training, potentially leading to more efficient exploration policies.

Summary updated

Abstract

Memory in reinforcement learning raises two problems. Attention finds the relevant item by scoring the whole store, which is costly for robots under latency and energy limits. When a retrieved memory pays off, credit for acquiring it must cross the whole sequence. We argue that both are governed by one quantity, the value of information, and propose to estimate it from archived rollouts with a learned world model. We obtain that, when read at the observation, it yields a provable lower bound on the optimal value of the acquiring action, which floors its TD target and attributes this floor to the observation that earned it. Read at the decision, it defines the optimal retrieval set. A pilot retrieval system, to be trained and improved with this signal, solves a memory task with reduced context.
BibTeX
@misc{strauss2026cheap,
  author = {Daniel Strauss and Nikolaos Sotirakis and Zhenshan Bing and Alois Knoll},
  title = {{Cheap Retrieval and Observation Credit Assignment from One Quantity: The Value of Information}},
  year = {2026},
  eprint = {2610.40030},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.40030},
}
Figure