Source-linked AI summary
Cheap Retrieval and Observation Credit Assignment from One Quantity: The Value of Information
Daniel Strauss, Nikolaos Sotirakis, Zhenshan Bing, Alois Knoll
TL;DR
Memory retrieval makes attention costly over large stores, while learning which observations to acquire requires credit assignment across long sequences. The paper proposes estimating information value from archived rollouts; at a decision it identifies what to retrieve, and at an observation it provides a lower bound on the acquiring action’s optimal value.
Problem
Memory creates a costly search over stored items, while learning which observations to acquire requires assigning credit across long sequences.
Source: §1 · p. 1Method
The paper estimates information value from archived rollouts as the change in achievable return when a decision gains access to recorded-history subsets.
Source: §1 · p. 1Results
Information value at an observation gives a lower bound on the optimal TD value of the action that acquired it.
Source: §2 · p. 3Takeaways & Limitations
The same information-value quantity links retrieval choice at a decision with credit for acquiring observations.
Source: §1 · p. 1Neither the information-value estimator nor the floored target is implemented, so faster convergence remains a hypothesis.
Source: §3 · p. 4
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction frames memory as both a costly retrieval problem and a long-horizon observation-credit problem. It proposes information value as a common basis for deciding what to retrieve and crediting observations that earn later value.
1 Introduction
- Information value is proposed as a common basis for memory retrieval and observation credit assignment.The paper contrasts this with credit methods that redistribute delayed rewards or infer earlier-action influence, including TVT’s use of later retrieval.Source: §1 · p. 1
- Dense attention grows costly with store size, while sparse retrieval leaves unselected items without gradient and consolidation may discard information needed later.Source: §1 · p. 1
- The proposed estimator learns information value from archived rollouts as the change in achievable return when a decision gains access to recorded-history subsets, also selecting what to retrieve.Source: §1 · p. 1
2 Consuming the Value of Information
Information value measures how recorded history changes achievable return, and learned world-model estimates support both credit assignment and memory retrieval. The section also describes a pilot retrieval system and its reduced-context task results.
Estimating information value
- A learned world model reuses archived trajectories by masking observations and estimating expected return under different knowledge states.The model learns how outcomes at a decision depend on rarely encountered information through supervised prediction on the archive.Source: §2 · p. 2
- Information value is the change in achievable return when recorded history becomes available, rather than the return of the current policy.The value compares decisions with and without specified history under respective knowledge states.Source: §2 · pp. 2–3
Credit assignment
- The information-credit term plus the attainable-return lower bound floors the optimal TD value of the action that acquired the information.The attainable-return bound applies when the later policy must ignore information collected by that action.Source: §2 · p. 3
Retrieval
- Approximation (a) updates the retrieved set once per environment step using the previously held set, and has not yet been empirically validated.The passage also notes that retrieval-set updates could instead run asynchronously from the policy.Source: §2 · p. 4
Memory Navigation
- Memory Navigation reached mean return 0.95 after 0.59M steps, versus 0.94M for Gaussian absolute-position retrieval and 1.38M without a retrieval head.It was fine-tuned on S17Random with a 5-token context after pretraining on MiniGrid-Memory-S9 with 64 tokens; only the full-context pretrained model was faster. Its persistent Memory Ghost retrieves through an external memory at a cost of one layer regardless of store size.Source: §2 · p. 4
3 Limitations
The proposed floor and its estimation remain unvalidated, and information value is not tied to causal notions of observation contribution. Estimation can also overstate the optimal value, while timestep indexing and information overlap constrain how credit is assigned.
3 Limitations
- The information-value estimator and floored target are not implemented, so faster convergence from the proposed update remains a hypothesis.The paper also does not relate information value to whether an observation was necessary for the selected action.Source: §3 · p. 4
- Model and regression errors, action maximization, and noisy supremum estimates can each push the estimated floor above Q∗.Restricting the retrieval set R to steps near s can reduce both cost and bias.Source: §3 · p. 4
- Because information value is defined under exploration policy µ, later actions may reveal masked history and reduce an observation’s credit.For archives from a changing policy, the policy version must be recorded in the history.Source: §3 · p. 4
- Timestep indexing can misallocate redundant and synergistic information: the supremum selects one R, crediting the larger component rather than their sum.The paper leaves open whether M∗t and bs,t arise from one common object, and proposes exploration information value as future work.Source: §3 · p. 4
A Expressions of U
The appendix expresses U as a value conditioned on recorded history and develops equivalent expressions by fixing exploration-policy actions before the decision, then optimizing the decision and continuation. The proof uses conditional expectations and the tower property.
A Expressions of U
- The policy constraint fixes actions before t to µ and restricts the action at t to depend on H_A; later policy rules may use the full H_{t+1}.The supremum separates the choice at t from the continuation, using the interchangeability principle.Source: A Expressions of U · p. 7
- Conditioning on H_{t+1} yields the next-step value expression, with the final equality following from the definition of Q∗_t.The proof also invokes the tower property for histories up to t and for a fixed action.Source: A Expressions of U · pp. 7–8
- U_t(A | B) is treated as a function of H_t, with the full-history case A = [t] expressed through Eq. (2).The cited definition passage specifies that U_t(A | B) is the value of choosing at t from H_A, evaluated with H_B.Source: A Expressions of U · pp. 7–8
B New Information Carries non-negative value
The proposition establishes that adding information cannot reduce value. Its proof compares values under nested information sets and shows that the inner term is at least the best optimal action value.
B New Information Carries non-negative value
- For nested information sets B ⊆ A, the proof lower-bounds the inner term by max_a Q∗_t(H_A, a), yielding the non-negative-value result.The proposition is described as a simple case of the Blackwell theorem [26].Source: B New Information Carries non-negative… · pp. 8–9
C Acquisition bound
The acquisition bound decomposes the value associated with an observation into a baseline and an observation-dependent component. The split reorganizes, rather than tightens, the floor; its proposed estimation benefit remains untested.
C Acquisition bound
- Proposition 4 gives an acquisition bound for t ≥ s, action a, and R ⊆ {s + 1, …, t}.Its derivation uses B_s and C_R to compare values with and without the selected history items.Source: C Acquisition bound · pp. 9–10
- The un-split floor depends on h_s and may require bootstrapped credit to travel from t across t − s + 1 steps, especially when h_s is rarely observed.The baseline L_s,t(a) masks everything acquired from s onward and can be fitted from every episode reaching t.Source: C Acquisition bound · p. 11
- The authors expect the split estimate to become informative earlier than an estimate of P_s,t(a) when Λ_t ≫ 0, but this benefit remains to be tested.The split changes estimation, not the exact bound.Source: C Acquisition bound · p. 11
- The split floor is a reorganization, not a tightening: for exact quantities it never exceeds P_s,t(a), with equality at R = ∅.Choosing R determines how much of the floor is credited to h_s, handling redundancy and synergy.Source: C Acquisition bound · p. 11
D Supplementary Material
Supplementary material provides rollout videos for Memory Navigation and describes how agents without a retrieval head cope with short context. The videos map environment state, Transformer activations, memory states, and token consumption across panels.
D Supplementary Material
- The implementation of Memory Navigation and all experiments is available in the linked repository.The passage supplies the repository address.Source: D Supplementary Material · p. 11
- Without a retrieval head, the agent waits a cue-dependent number of steps to retain the cue in its temporal embedding, or follows a cue-dependent path to retain it in recent observations.The path-based behavior is shown with positional embeddings removed and a context of 3 tokens.Source: D Supplementary Material · p. 11
- Table 1’s panels progress from environment state and Transformer activations to memory states and token consumption.Purple marks attention, the red triangle the agent, and the orange rectangle the Memory Ghost.Source: Table 1 · p. 11