RoMeRL: Balancing Feedback Coverage and the Memory-Reward Trap in Self-Evolving Agent Memory via Reduced-Order Utility States

AI summary

Overview

• Research area: Reinforcement learning for self-evolving LLM agent memory systems (memory utility learning, credit assignment, exploration–exploitation in retrieval).
• Technical level: Advanced. The paper combines an applied agent-memory system with formal definitions, three theorems, and a proposition with proofs in an appendix.
• Scope: The paper diagnoses a failure mode it calls the Memory-Reward Trap, proposes a fixed four-coordinate memory state (RoMeRL) in place of trajectory-indexed utilities, and evaluates it on three agent benchmarks with frozen LLM backbones.

What This Paper Is About

Learning-based agent memory typically assigns a separate utility value to every stored trajectory and updates those values from task-level rewards. The paper argues this design causes two coupled problems: the learnable utility state keeps growing with interaction history (diluting feedback across an ever-larger space), and because rewards are assigned jointly to all co-retrieved memories, irrelevant or outdated experiences can receive positive updates they did not earn. The goal is to improve feedback coverage without expanding the set of utility variables exposed to this misattributed reward, by representing each task's memory utility with a small, fixed number of semantic coordinates instead.

Key Contributions

1. Diagnosis of trajectory-indexed memory learning. The paper shows that as the utility state grows, feedback is diluted across more variables, and the persistent support exposed to the memory-reward trap grows with the memory-state dimension.
2. The RoMeRL method. RoMeRL replaces each task's growing trajectory-indexed utility space with a fixed-dimensional per-task state factorized by outcome polarity (positive/negative) and memory dynamics (consolidated/adaptive), yielding four semantic coordinates.
3. Theoretical characterization of the feedback–trap balance. The paper proves a gap–variance decomposition of memory utility, a sufficient feedback budget for full-pool estimation, a feedback-concentration result under state reduction, and a steady-state bound on erroneous-coordinate occupancy.
4. Empirical evaluation across three agent domains. RoMeRL is tested on LifelongAgentBench (OS and DB tasks), ALFWorld (six task types), and AppWorld, with ablations, an MRT stress test, cross-model memory transfer, and efficiency analysis.

Main Findings

• Highest overall average score: RoMeRL reaches an overall macro-average of 0.753, compared with 0.724 for MemRL, the strongest baseline evaluated on all three benchmarks, an improvement of 2.9 percentage points. The no-memory baseline scores 0.672, RAG 0.667, Mem0 0.685, and MemP 0.701.
• Benchmark-specific results: On LifelongAgentBench, RoMeRL scores 0.824 / 0.838 (Last-Epoch SR / CSR) on OS and 0.680 / 0.952 on DB, versus MemRL's 0.808 / 0.820 and 0.632 / 0.934. On ALFWorld it reports 0.968 (P&P), 0.957 (Examine), 0.901 (Clean), 0.862 (Heat), 0.880 (Cool), and 0.826 (Pick-2). On AppWorld it improves SGC from 0.286 to 0.326 (a 4.0 percentage-point gain) while TGC is 0.306 versus MemRL's 0.313.
• Feedback utilization improves: MemRL's Cold-Q ratio rises from roughly 29% to 44.9%, whereas RoMeRL reduces it from roughly 28% to 9.0%, an 80.0% reduction, while raising feedback density from 4.96 to 29.93 (approximately 6.0×).
• Efficiency gains: Compared with MemRL, RoMeRL reduces average LLM calls by 120K, from 570K to 450K (21.1%), and reduces memory-pool size by 38K, from 45K to 7K (84.4%).
• Reduced reward contamination under stress: In a controlled MRT stress test on the OS task with a first-round memory pool containing 10% noisy entries and results reported after ten training rounds, MemRL reaches 79.2% round-10 SR with 3.7 positive noise updates and a 1.02% final noise ratio. Adding UCB raises positive noise updates to 7.2 and the final noise ratio to 1.20% while lowering SR to 78.4%. RoMeRL limits these to 2.4 and 0.15% while achieving the highest SR of 82.0%.
• Cross-model memory transfer: Transferring the frozen memory state improves scores and reduces average steps in all four reported model–task combinations: GPT-5.4-mini on OS moves from 67.0 / 3.23 to 81.6 / 2.22 (+14.6 / −1.01); Gemini-3.5-flash on OS from 74.0 / 4.53 to 81.4 / 3.02 (+7.4 / −1.51); GPT-5.4-mini on DB from 93.0 / 2.15 to 96.8 / 2.00 (+3.8 / −0.15); and Gemini-3.5-flash on DB from 96.2 / 2.44 to 97.6 / 2.18 (+1.4 / −0.26).
• Ablation results: Removing the Negative Consolidated Coordinate (NCC) lowers both Last-Epoch SR and CSR; NCC accounts for 27.14% of occupied coordinates on OS and 42.78% on DB. Removing the Positive Adaptive Coordinate (PAC) mainly reduces Last-Epoch SR with little change in CSR; PAC occupies 8.21% of coordinates on OS and 5.05% on DB.
• Theory: State reduction makes each coordinate receive on average N_t/4 times more feedback than under trajectory-indexed learning, and changes average utility-estimation variance from O(σ²N_t / kT) to O(4σ² / kT). Under a generic clean–erroneous transition model with clean-to-erroneous probability at most γ and erroneous-to-clean probability at least λ > 0, the steady-state erroneous fraction is at most γ/(γ+λ) and the expected number of erroneous active coordinates is at most dγ/(γ+λ).

Methodology in Plain English

The authors first formalize what existing outcome-driven memory methods do: each stored trajectory gets its own utility value, updated toward the task reward whenever that trajectory is retrieved. They separate the utility a memory actually contributes (its marginal effect, measured by comparing outcomes with and without it) from the raw-return signal that bundle-level rewards produce (which also absorbs the baseline difficulty of the task and correlations among co-retrieved memories). Their first theorem shows more retrieval reduces estimation variance but cannot remove that baseline-and-attribution gap, and their second shows the feedback needed to estimate a growing pool of utilities scales with the pool size.

Their fix is a change of state representation rather than more exploration. For each task, instead of one utility per stored trajectory, they maintain a 2 × 2 state with four coordinates: Positive Consolidated (PCC, the most efficient successful trajectory seen), Positive Adaptive (PAC, the earliest success observed after the first failure), Negative Consolidated (NCC, a failed trajectory whose utility has risen above the negative initialization threshold), and Negative Adaptive (NAC, the most recent failure). Each coordinate holds one representative trajectory plus its utility; new experiences update or replace coordinate contents rather than adding new variables.

Retrieval ranks these active candidates by a weighted combination of embedding similarity to the query and their learned utility, then takes the top k_ret. After the episode, each retrieved coordinate's utility is updated with the standard exponential Q update using the task reward and learning rate. When a representative is replaced, the incoming trajectory inherits the current utility as a warm start (with its post-admission update count reset), and later outcomes adapt it. This keeps the active retrieval support at most four memories per task. The authors evaluate against RAG, Mem0, MemP, Pass@k, and MemRL with frozen backbones, plus ablations, a noise-injection stress test, and cross-model transfer experiments.

Why This Matters

Impact on research. The paper reframes agent-memory improvement as a state-representation problem rather than an exploration problem. It gives a formal account of why stronger exploration in outcome-driven memory systems can raise metric coverage while degrading performance, and it supplies bounds that separate statistical uncertainty from attribution bias. This is a distinct argument from the usual "explore more to reduce cold start" advice, and it connects memory design to long-standing causal credit-assignment questions in RL.

Real-world applications.

• Long-running LLM agents that interact with operating systems and databases and must accumulate reusable procedure across sessions.
• Embodied or household-planning assistants that need to recover from failed attempts and remember what worked after a failure.
• Multi-application workflow agents that compose tool calls across services and benefit from compact, low-noise procedural memory.
• Cost-sensitive deployments where a frozen backbone is used and memory is the only learnable component, so memory size and LLM call volume directly drive operating cost.

Industry relevance. The reported reductions in memory size (84.4%) and LLM calls (21.1%) target the two resource costs that dominate production agent deployments: storage of a growing memory pool and inference invocations. Because the LLM backbone is never updated, the method can be layered onto existing frozen-model pipelines, and the cross-model transfer results suggest a memory state learned with one model can be reused with another.

Future Directions

• Causal credit assignment remains open. The authors state that RoMeRL still relies on outcome-level rewards and does not fully resolve causal attribution.
• Estimating the transition quantities γ and λ. Proposition 1's occupancy bound needs the clean-to-erroneous and erroneous-to-clean transition rates, which the authors say require coordinate-level causal labels from paired counterfactual rollouts or equivalent attribution methods.
• Combining attribution with finer-grained rewards. The conclusion proposes pairing such attribution signals with finer-grained reward shaping.
• Open-ended, longer-horizon evaluation. The paper calls for testing in more open-ended and longer-horizon settings than the three benchmarks studied.

Target Audience

Researchers and engineers working on LLM agent memory, reinforcement learning for language agents, and retrieval-augmented agent systems. The paper is also relevant to practitioners who deploy agents where memory growth and inference cost matter, and to readers interested in formal treatments of credit assignment and reward misattribution in non-parametric or memory-only learning. Portions of the paper assume comfort with Q-learning updates, interventional notation, Hoeffding bounds, and union-bound arguments.

Authors’ abstract

Learning-based memory systems for self-evolving LLM agents face two tightly coupled challenges. First, trajectory-indexed utilities grow with the interaction history, thereby dispersing limited feedback over an ever-expanding state space. Second, because trajectory-level rewards are jointly assigned to co-retrieved memories, irrelevant experiences may receive misleading utility updates and consequently enter the memory-reward trap. To address these challenges, we introduce Reduced-Order Memory Reinforcement Learning (RoMeRL), which represents the growing trajectory-indexed utility space using a fixed-dimensional per-task memory state factorized by outcome polarity and memory dynamics. RoMeRL incorporates new experiences through a fixed set of semantic coordinates whose contents are updated or replaced over time, thereby concentrating feedback over a bounded utility support. Theoretically, we show that this reduced-order parameterization increases the average feedback received by each utility coordinate and characterize the steady-state occupancy of erroneous coordinates under a generic coordinate-transition model. Empirically, across ALFWorld and LifelongAgentBench, RoMeRL improves task performance, reduces the Cold-Q ratio by 80.0%, increases feedback density by approximately 6.0 times, reduces the maintained memory size by 84.4%, and cuts LLM calls by 21.1%. These results show that reduced-order utility states support efficient self-evolving agent memory while limiting persistent reward contamination. Code is available at: https://github.com/YOUNG-fnxm/RoMeRL