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

Source: arXiv:2608.02508 · Published 2026-08-03 · By Yi Yang, Zhennan Chen, Yihong Zhuang, Tiehan Fan, Yinan Chen, Jian Li et al.

TL;DR

This paper tackles foundational challenges in learning-based memory systems for large language model (LLM) agents that evolve themselves through continual interaction. Two key problems are identified: (1) as interaction history grows, trajectory-indexed utility representations expand the state space unboundedly, diluting limited task-level feedback among many memory entries; (2) trajectory-level rewards are assigned jointly to all co-retrieved memories, causing irrelevant or weakly contributing memories to receive misleading positive utility updates, a phenomenon called the memory-reward trap (MRT). To address this, the authors propose RoMeRL (Reduced-Order Memory Reinforcement Learning), which replaces the growing trajectory-indexed utility space with a fixed-dimensional per-task memory state factorized by outcome polarity (success/failure) and memory dynamics (consolidated/adaptive). This yields only four semantic coordinates per task, each storing a representative trajectory and utility, with contents updated or replaced over time. This reduced-order approach concentrates scarce feedback over a bounded utility support and limits persistent reward contamination by erroneous memories. Theoretically, they characterize how this factorization increases per-utility feedback concentration and controls erroneous coordinate occupancy under coordinate transition dynamics. Empirical evaluation on ALFWorld and LifelongAgentBench benchmarks shows RoMeRL improves overall task success rate by 3.2 percentage points versus strong memory-learning baselines, reduces the cold-start utility ratio by 80%, increases feedback density sixfold, shrinks memory size by 84.4%, and lowers calls to the underlying LLM by 21.1%. Ablations demonstrate complementary roles of the factorized coordinates in capturing positive and negative experience dynamics. The results show that reduced-order utility states form an efficient and robust agent memory design that mitigates the exploration-contamination tradeoff inherent in trajectory-indexed utility learning.

Key findings

• RoMeRL reduces the Cold-Q ratio (proportion of representatives with no direct utility update) from ~28% to 9.0% on the OS task, an 80% relative reduction.
• Feedback density per memory coordinate increases approximately 6.0 times under RoMeRL versus MemRL on OS, rising from 4.96 to 29.93 updates per coordinate.
• RoMeRL reduces the memory pool size by 84.4%, from 45K to 7K maintained memories, drastically lowering memory footprint.
• The number of LLM calls required decreases by 21.1%, from 570K to 450K, lowering inference cost without updating the LLM.
• RoMeRL achieves an overall average success rate of 0.862 across ALFWorld and LifelongAgentBench, a 3.2% absolute improvement versus MemRL's 0.830.
• In a controlled Memory-Reward Trap stress test on the OS task with 10% noisy memories, RoMeRL limits positive noise updates to 2.4 and final noise ratio to 0.15%, outperforming MemRL (3.7 and 1.02%) and MemRL with UCB exploration (7.2 and 1.20%).
• Cross-model memory transfer experiments show frozen RoMeRL state improves both validation scores and reduces average execution steps across different LLM backbones.
• Ablations show removing the Negative Consolidated Coordinate lowers success rate and cumulative success rate, indicating its role capturing reusable negative experience. Removing the Positive Adaptive Coordinate mostly lowers last-epoch success rate, showing it supports capturing recovery transitions.

Threat model

Adversaries are not explicitly modeled in this paper since the focus is on the internal learning and feedback dynamics of self-evolving agent memory. The implicit threat is that noisy or irrelevant memories may be unintentionally reinforced by outcome-driven utility updates, causing contamination. The assumed adversary is the reward misattribution inherent in trajectory-level co-retrieval without granular attribution. The method constrains this intrinsic threat but does not address external adversarial manipulations or attacks.

Methodology — deep read

The paper begins by formalizing the problem of trajectory-indexed utility learning in agent memories, where each stored trajectory memory is assigned a utility updated via standard Q-learning style updates based on task-level rewards. The challenge is that as trajectories accumulate, the memory utility space dimension grows unboundedly, causing feedback to thin out and increasing the chance of misattributed reward updates, defined as the memory-reward trap (MRT). The MRT occurs when memories with no positive marginal contribution nonetheless receive positive observational utility due to joint reward assignment with co-retrieved memories, thus causing erroneous reinforcement.

The authors theoretically analyze this setting by decomposing the utility estimation error into the sum of the observational attribution bias and sampling variance. They prove that more exploration reduces variance but cannot reduce attribution bias or the task-level baseline, highlighting a fundamental limitation in trajectory-indexed utility estimation.

To address this, RoMeRL compresses the growing utility state into a fixed-dimensional (4-dimensional) factorized state per task, given by the Cartesian product of outcome polarity (positive/negative) and memory dynamics (consolidated/adaptive). This yields four semantic coordinates: Positive Consolidated (PCC), Positive Adaptive (PAC), Negative Consolidated (NCC), and Negative Adaptive (NAC). Each coordinate stores a representative trajectory and its current utility estimate.

New trajectories update or replace coordinates based on criteria such as global efficiency, temporal transition from failure to success, or utility thresholds, controlling memory population size and content freshness. The utilities of coordinates are updated online via Q-learning updates weighted by retrieval presence and outcomes.

The authors mathematically characterize (Theorem 3) that the feedback budget concentrates approximately kT/d updates per coordinate (d=4 here) under a fixed total interaction budget T, substantially improving the average number of updates per utility compared to full trajectory-indexed state of growing dimension N_t. They also model steady-state occupancy of erroneous coordinates under generic coordinate transition probabilities for contamination and correction and prove the expected erroneous coordinate count is bounded and typically much lower than in the full-pool case.

Practically, the system embeds trajectories semantically and ranks them for retrieval based on similarity and utility weighted scores, forming the set of memories retrieved as context for the underlying frozen LLM agent, whose parameters are not updated. RoMeRL replaces the underlying LLM memory reinforcement learning module.

Evaluation is conducted on ALFWorld and LifelongAgentBench benchmarks, which provide diverse embodied planning, OS interaction, and database tasks. They compare against retrieval-based, agentic memory, and other memory-reinforcement learning baselines with frozen LLMs, measuring task success rate (SR), cumulative success rate (CSR), feedback density, cold start ratio, LLM calls, and memory pool size. Ablations remove individual coordinates to isolate their contributions.

Code is publicly released, but datasets are standard benchmarks and not proprietary.

Overall, the methodology carefully isolates the challenges of feedback dilution and reward credit misassignment in trajectory-indexed memory learning, proposes a mathematically justified fixed-dimensional factorization of the utility state, implements a practical online update supporting retrieval scoring, and evaluates comprehensively in realistic multitask agent settings.

Technical innovations

• Identification and formalization of the Memory-Reward Trap (MRT), a critical issue where joint trajectory-level rewards misattribute utility to weakly relevant memories leading to persistent reward contamination.
• Proposing a reduced-order memory utility state factorized by outcome polarity (positive/negative) and memory dynamics (consolidated/adaptive) that fixes the utility state dimensionality per task regardless of interaction history length.
• Mathematical characterization of feedback concentration benefits and bounding erroneous coordinate occupancy under generic state transition models, providing theoretical backing for reduced-order state efficiency and robustness.
• Practical algorithm design implementing the four semantic coordinate memory states with online retention, promotion, replacement operations and Q-value utility update combined with retrieval scoring.
• Empirical demonstration that reduced-order utility states substantially increase feedback density and reduce cold start ratios while shrinking memory size and cutting inference cost without LLM fine-tuning.

Datasets

• ALFWorld — large-scale embodied agent environment for instruction following and interaction tasks — public
• LifelongAgentBench (OS and DB tasks) — multi-task benchmark including operating system and database management subtasks — public

Baselines vs proposed

• MemRL: Overall success rate = 0.830 vs RoMeRL: 0.862
• MemRL Cold-Q ratio on OS task = ~29% rising to 44.9% vs RoMeRL reducing from ~28% to 9.0%
• MemRL feedback density on OS = 4.96 updates per memory vs RoMeRL = 29.93 (6× increase)
• MemRL memory pool size = 45K entries vs RoMeRL = 7K (84.4% reduction)
• MemRL LLM calls = 570K vs RoMeRL = 450K (21.1% reduction)
• In controlled MRT stress test, MemRL positive noise updates = 3.7, final noise ratio = 1.02% vs RoMeRL = 2.4 and 0.15%
• MemRL + UCB exploration increased positive noise updates to 7.2 and noise ratio to 1.20%, performing worse than RoMeRL

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2608.02508.

Fig 1: Memory-reward trap: Stronger explo-

Fig 2: Overview of RoMeRL. Top: the agent retrieves memories to construct the LLM context and

Fig 4: Coordinate ablation on the OS task.

Fig 6: Final Q-value composition on OS tasks for the MemRL baseline (Left) and RoMeRL

Fig 7: LLM calls per section on the DB and OS task. RoMeRL achieves lower and steadily

Limitations

• RoMeRL relies on task-level outcome rewards and does not fully solve true causal credit assignment for individual memory contributions.
• The theoretical bounds on erroneous occupancy require estimation of contamination and correction rates (γ and λ), which need causal labels or counterfactual rollouts hard to obtain in practice.
• Experiments do not evaluate fully open-ended, longer-horizon tasks where utility dynamics may be more complex.
• No adversarial evaluation against intentional reward manipulation or memory poisoning is performed to stress-test robustness.
• The fixed 4-coordinate factorization may limit expressiveness or require further tuning for domains with more nuanced outcome or memory dynamics.
• The approach assumes stationarity of raw-return targets in its theoretical analysis, which may not hold in rapidly changing environments.

Open questions / follow-ons

• How can causal credit assignment for memory utilities be improved beyond outcome-level rewards to fully resolve the memory-reward trap?
• What are effective approaches to estimate or learn the contamination and correction transition probabilities (γ and λ) without costly counterfactual rollouts?
• Can the fixed factorized coordinate design be extended or adapted to handle more complex or multi-dimensional outcome signals or memory dynamics?
• How does RoMeRL perform in fully open-ended continual learning settings with longer-horizon dependencies and evolving reward structures?

Why it matters for bot defense

Bot-defense and CAPTCHA practitioners designing self-evolving LLM agents can directly benefit from this work by adopting reduced-order memory utility representations that concentrate feedback and reduce reinforcement of irrelevant or noisy memories. The explicit factorization by outcome polarity and adaptive/consolidated dynamics provides a principled framework to manage agent memory size and control error propagation without retraining LLMs. This can improve agent robustness and efficiency under limited feedback budgets common in interactive security or verification workflows. The memory-reward trap analysis highlights the potential pitfalls in naive trajectory-indexed utility learning, guiding engineers to better design feedback assignment mechanisms and update policies. The empirical results demonstrating lower memory footprint, fewer LLM calls, and improved success rates offer practical motivation to implement similar memory compression and factorization strategies in security-critical autonomous agents or CAPTCHA solvers adapting over time.

Cite

@article{arxiv2608_02508,
  title={ RoMeRL: Balancing Feedback Coverage and the Memory-Reward Trap in Self-Evolving Agent Memory via Reduced-Order Utility States },
  author={ Yi Yang and Zhennan Chen and Yihong Zhuang and Tiehan Fan and Yinan Chen and Jian Li and Jian Yang and Ying Tai },
  journal={arXiv preprint arXiv:2608.02508},
  year={ 2026 },
  url={https://arxiv.org/abs/2608.02508}
}

Read the full paper

• arXiv:2608.02508 (abstract)
• arXiv:2608.02508 (PDF)