MemRL: Self-Evolving Agents via Runtime Reinforcement Learning on Episodic Memory — part 2/6

Cleaned-text code points [15690, 31467). Bibliography omitted here; source.md includes it.

Standard RAG systems assume “similar implies useful,” but agentic tasks often involve environment-specific routines that generalize poorly ( Singh et al., 2025 ; Cuconasu et al., 2024 ; Gan et al., 2024 ; Zhou et al., 2024 ) . Therefore, MemRL implements a Two-Phase Retrieval strategy. Phase A: Similarity-Based Recall. Given query s s , we isolate a candidate pool 𝒞 ⁡ ( s ) \mathcal{C}(s) of semantically consistent experiences by filtering memory bank ℳ \mathcal{M} via cosine similarity and a sparsity threshold δ \delta : 𝒞 ⁡ ( s ) = TopK k 1 ​ ( { i | s ​ i ​ m ​ ( E ​ m ​ b ​ ( s ) , E ​ m ​ b ​ ( z i ) ) > δ } ) , \mathcal{C}(s)=\text{TopK}_{k_{1}}(\{i|sim(Emb(s),Emb(z_{i}))>\delta\}), (6) where E ​ m ​ b Emb represents the Embedding Model to transfer the raw text to a vector. If 𝒞 ⁡ ( s ) = ∅ \mathcal{C}(s)=\emptyset , MemRL relies solely on the frozen LLM for exploration. Phase B: Value-Aware Selection. To determine the final context ℳ c ​ t ​ x ​ ( s ) \mathcal{M}_{ctx}(s) , we select top- k 2 k_{2} items from 𝒞 ⁡ ( s ) \mathcal{C}(s) using a composite score balancing exploration (similarity) and exploitation (utility Q Q ): score ​ ( s , z i , e i ) = ( 1 − λ ) ⋅ s ​ i ​ m ^ ​ ( E ​ m ​ b ​ ( s ) , E ​ m ​ b ​ ( z i ) ) + λ ⋅ Q i ^ . \text{score}(s,z_{i},e_{i})=(1-\lambda)\cdot\hat{sim}(Emb(s),Emb(z_{i}))+\lambda\cdot\hat{Q_{i}}. (7) where ⋅ ^ \hat{\cdot} denotes z-score normalization and λ ∈ [ 0 , 1 ] \lambda\in[0,1] modulates the trade-off. This mechanism filters out “distractor” memories—those semantically similar but with low historical utility. As detailed in Section 5.4.2 , normalization and strict similarity thresholds are essential for noise filtering and maintaining stability during self-evolution.

### 4.3 Non-Parametric RL on Memory

The core of MemRL is the continuous refinement of Q-values based on environmental feedback, enabling the agent to “remember” what works. During runtime, MemRL performs learning entirely in memory space. With the retrieved context m m , the agent samples an action a a according to the policy π \pi defined in Eq. 1 . Executing a a then yields an environmental reward r r (e.g., execution success or scalar score). For the memories actually injected into the input context ℳ ctx ​ ( s ) \mathcal{M}_{\text{ctx}}(s) , we update their utilities in triplets with a Monte Carlo style rule, i.e., the Eq. 4 , following the runtime learning loop shown in Figure 3 . This update drives Q new Q_{\text{new}} toward the empirical expected return of using experience e i e_{i} under similar intents. Meanwhile, for each sampled trajectory, we use an LLM to summarize the experience ( Fang et al., 2025 ) , and write it back into the memory bank as a new triplet ( z , e new , Q init ) (z,e_{\text{new}},Q_{\text{init}}) , enabling continual expansion of experience while keeping the LLM parameters unchanged.

### 4.4 Theoretical Stability Analysis

We analyze the stability of MemRL from a reinforcement learning perspective, with full analysis provided in Appendix A . We posit two standard assumptions: a frozen inference policy p LLM p_{\mathrm{LLM}} and a stationary task distribution. Under these conditions, the learning target β ( s , m ) = 𝔼 [ r t | s , m ] \beta(s,m)=\mathbb{E}[r_{t}|s,m] is well-defined, where the expectation is taken over the stochastic rewards resulting from the Inference Policy p L ​ L ​ M p_{LLM} distribution. We prove that utility estimates updated via Eq. 4 are unbiased and variance-bounded ( Sutton and Barto, 2018 ) . Specifically, as t → ∞ t\to\infty : lim t → ∞ 𝔼 ⁡ [ Q t ] \displaystyle\lim_{t\to\infty}\mathbb{E}[Q_{t}] = β ⁡ ( s , m ) , \displaystyle=\beta(s,m), (8) lim sup t → ∞ Var ⁡ ( Q t ) \displaystyle\limsup_{t\to\infty}\mathrm{Var}(Q_{t}) ≤ α 2 − α ​ Var ​ ( r t ∣ s , m ) . \displaystyle\leq\frac{\alpha}{2-\alpha}\mathrm{Var}(r_{t}\mid s,m).

Furthermore, we address the challenge of the latent retrieval distribution Pr ⁡ ( s | m ) \Pr(s|m) shifting during training by framing MemRL as a Generalized Expectation-Maximization (GEM) ( Dempster et al., 1977 ) process. The system performs coordinate ascent on a global objective: the retrieval ranking acts as the Policy Improvement (E-step), while the utility update acts as the Value Update (M-step). By the monotonic improvement theorem ( Neal and Hinton, 1998 ) , the system converges to a stationary point where the global memory utility stabilizes: lim t → ∞ 𝔼 [ Q t ( m ) ] = ∑ s ∈ 𝒮 ⁡ ( m ) 𝔼 [ r | s , m ] Pr ( s | m ) . \lim_{t\to\infty}\mathbb{E}[Q_{t}(m)]=\sum_{s\in\mathcal{S}(m)}\mathbb{E}[r|s,m]\Pr(s|m). (9) where 𝒮 ⁡ ( m ) \mathcal{S}(m) is the effective support set of the memory. This formulation guarantees global stability and prevents catastrophic forgetting. Details can be found in Appendix A.4 .

## 5 Experiments

### 5.1 Experimental Setup

Baselines & Benchmarks. We compare MemRL against RAG-based (RAG, Self-RAG), Agentic Memory (Mem0, MemP), and Test-Time Scaling (Pass@ k k ) baselines under a frozen-backbone setting (see Appendix D.1 ). Evaluations span four domains: BigCodeBench (coding), ALFWorld (navigation), LifelongAgent Bench (OS/DB), and Humanity’s Last Exam(HLE). Details are in Appendix D.2 . Backbones are selected per benchmark to avoid no-signal or ceiling problems, ensuring valid learning signals, while Appendix E.4 provides a unified comparison to demonstrate cross-task consistency under identical capacity.

Metrics. We employ two metrics: (1) Success Rate (SR) , the ratio of tasks completed in an epoch; (2) Cumulative Success Rate (CSR) , the proportion of tasks solved at least once across epochs.

We evaluate our MemRL and baselines under two distinct settings: Runtime Learning , which assesses the ability to learn and adapt within a training session, and Transferring , which evaluates the generalization capability of the learned memory on unseen tasks. Implementation and reproducibility details, including all prompts used in our experiments, can be found in Appendix E and Appendix I .

### 5.2 Main Results

##### Runtime Learning Results.

As detailed in Table 1 , MemRL demonstrates robust superiority across all domains, surpassing the strongest baseline (MemP) by an average of + 3.8 % +3.8\% in Cumulative Success Rate (CSR). The gains are most significant in exploration-intensive environments like ALFWorld and OS tasks (both + 6.2 % +6.2\% ), while maintaining a steady lead on the challenging HLE benchmark ( + 3.6 % +3.6\% ). This confirms that our value-based mechanism, unlike MemP’s heuristic retrieval, effectively filters noise to retain high-utility procedural patterns.

##### Transferring Results.

We evaluate memory transferability by freezing the memory bank after training and testing on held-out sets. As shown in Table 2 , MemRL exhibits superior transferability, outperforming the strongest baseline (MemP) by an average of + 2.8 % +2.8\% in Success Rate. The advantage is particularly pronounced in complex environments like ALFWorld ( + 5.8 % +5.8\% ) and OS tasks ( + 2.6 % +2.6\% ). These margins validate that our Two-Phase Retrieval effectively filters low-value noise, retaining high-utility procedural patterns that generalize robustly to unseen scenarios.

### 5.3 Ablations

#### 5.3.1 Effectiveness of Runtime RL

To isolate the efficacy of runtime RL, we compare MemRL and its RAG-based variant against their non-RL counterparts (MemP and standard RAG) in the OS interaction environment. As shown in Figure 4 , while initial performance is comparable, a clear divergence emerges as training progresses: MemRL achieves a smoother learning curve and superior stability. Crucially, this advantage is most pronounced in the Cumulative Success Rate (dashed lines), where the monotonic widening gap indicates that the RL-driven value function effectively filters noisy memories and consolidates successful experiences.

#### 5.3.2 Impact of Q-Value Weighting

To determine the optimal equilibrium between semantic grounding and value-based exploitation, we evaluate the Q-weighting factor λ ∈ { 0 , 0.25 , 0.5 , 0.75 , 1 } \lambda\in\{0,0.25,0.5,0.75,1\} . As shown in Figure 5 , performance exhibits a clear concave trend peaking at λ = 0.5 \lambda=0.5 . Deviating toward extremes degrades results: pure semantic retrieval ( λ = 0 \lambda=0 ) plateaus due to an inability to filter functional distractors, while excessive RL weight ( λ → 1 \lambda\to 1 ) induces volatility and context detachment. This confirms that λ = 0.5 \lambda=0.5 represents an effective balance, where semantic similarity guarantees content relevance and Q-value ensures its helpfulness.

#### 5.3.3 Ablation Analysis: Cross-Task vs. Single-Task Optimization

To investigate the source of our performance gains, we conduct an ablation study in Table 3 by restricting the memory retrieval scope. We compare the full MemRL ( Cross-Task Retrieval ) against an ablated setting that only utilizes feedback from the single task instance, conceptually equivalent to Reflexion ( Shinn et al., 2023 ) . MemRL demonstrates superior performance in structured environments, particularly on OS-Agent ( + 9.0 % +9.0\% ) and ALFWorld ( + 5.1 % +5.1\% ). These benchmarks exhibit high intra-dataset similarity, allowing MemRL to effectively perform horizontal transfer —retrieving and adapting successful policies from semantically similar historical tasks. While on the HLE benchmark, the single-task baseline ( 0.610 0.610 ) is tied with MemRL ( 0.606 0.606 ). We attribute this to the HLE dataset’s low internal semantic similarity ( 0.186 0.186 ), as detailed in Appendix B.3 . This prevents effective cross-task generalization, forcing the agent to rely solely on single feedback.

#### 5.3.4 Sensitivity to Retrieval Size ( k 1 k_{1} and k 2 k_{2} ).

To investigate the impact of retrieval bandwidth, we compare three memory density configurations on the HLE (CS/AI) subset benchmark: sparse ( k 1 = 3 , k 2 = 1 k_{1}=3,k_{2}=1 ), moderate ( k 1 = 5 , k 2 = 3 k_{1}=5,k_{2}=3 ), and dense ( k 1 = 10 , k 2 = 5 k_{1}=10,k_{2}=5 ). As shown in Figure 6 , performance follows an inverted-U trajectory, illustrating the trade-off between information sufficiency and context noise. The sparse setting limits performance due to insufficient guidance, whereas the dense setting degrades success rate by introducing distractions into the reasoning context. Consequently, the moderate configuration ( k 1 = 5 , k 2 = 3 k_{1}=5,k_{2}=3 ) achieves the best result, effectively maximizing the signal-to-noise ratio of the retrieved context.

### 5.4 Discussion

In this section, we delve deeper into the mechanisms driving MemRL ’s performance, connecting empirical results to the challenge of balancing knowledge retention and adaptation.

#### 5.4.1 Predictive Power of the Q Critic

As shown in Figure 7(a) , the learned Q-values exhibit a strong positive correlation (Pearson r = 0.861 r=0.861 ) with empirical task success rates, rising from 21.5 % 21.5\% in the lowest-confidence bin to 88.1 % 88.1\% in the highest, which confirms the Critic’s ability to effectively rank memories by success likelihood. Beyond simple ranking, memory composition analysis (Figure 7(b) ) reveals that the agent retains a small fraction of “failure” memories ( ∼ 12 % \sim 12\% ) even in high-Q bins ( 0.9 − 1.0 0.9-1.0 ), suggesting that Q-values capture utility beyond binary outcomes by recognizing strategically useful near-misses. We further substantiate this with concrete case studies in Appendix H . This indicates that the Critic prioritizes reusable guidance—including transferable procedural lessons from high-utility failures—rather than merely separating success from failure, thereby offering greater robustness than simple success-replay mechanisms.

#### 5.4.2 Stability of MemRL

We analyze MemRL through the lens of the stability-plasticity dilemma . The superior CSR (Table 1 ) confirms that MemRL effectively expands the solution space, enabling the agent to break through local optima. Furthermore, long-term dynamics (Figure 8 ) reveal a critical stability advantage: while heuristic methods like MemP suffer from catastrophic forgetting—evidenced by a widening gap between CSR and current Success Rate— MemRL maintains synchronized growth. This is theoretically guaranteed by our stability analysis in Section 4.4 , which constrains the policy to improve monotonically without drift.

We quantitatively validate these insights using the Forgetting Rate , defined as F ​ R = N lost / N fail FR=N_{\text{lost}}/N_{\text{fail}} , where N lost N_{\text{lost}} denotes tasks transitioning from previous success to current failure and N fail N_{\text{fail}} is the total number of failures in the current epoch (see Figure 9 in Appendix B.1 for the full trajectory). MemRL achieves the lowest mean forgetting rate ( 0.041 0.041 ), outperforming MemP ( 0.051 0.051 ). Additionally, ablation results demonstrate that removing z-score normalization and similarity gating causes the rate to spike to 0.073 0.073 . This confirms that strict filtering is essential to manage utility variance and ensure that self-evolution remains stable.

#### 5.4.3 Extended Analysis.

We conduct further investigations to characterize the underlying mechanisms and generalization of MemRL . Specifically, Appendix B analyzes MemRL ’s role as a structural trajectory verifier and the correlation between task similarity and performance gains. Additionally, evaluations of advanced capabilities—including cross-model memory transferability and modular multi-task merging—are detailed in Appendix C , demonstrating MemRL ’s versatility and its capacity for modular capability expansion. We also analyze the cost and efficiency of MemRL in Appendix F .

## 6 Limitations and Conclusion

##### Limitations and Future Work.

While MemRL establishes a foundation for non-parametric evolution, its runtime dynamics reveal several promising avenues. (i) The current step-wise update, though fast, may introduce high-variance noise in long-horizon trajectories, inspiring us to explore multi-step updates or periodic memory consolidation. (ii) Credit-assignment ambiguity during utility updates, especially with multiple referenced experiences, raises the need for more precise attribution methods like Shapley methods ( Shapley and others, 1953 ) or value decomposition in multi-agent reinforcement learning ( Rashid et al., 2020 ; Sunehag et al., 2017 ) . (iii) While MemRL improves with increasing task exposure, performance may drift toward reflection-like behavior when task similarity is low, highlighting the need for a sufficiently diverse yet relevant experience base; for industrial deployment, ensuring high task density and hierarchical abstraction may be crucial. Further detailed discussions on these and other challenges, including memory security, dedicated domains, and multi-agent memory sharing, are provided in Appendix G .

##### Conclusion.

We proposed MemRL , a non-parametric approach reconciling the stability-plasticity dilemma by treating memory retrieval as a value-based decision process. Through the Intent-Experience-Utility triplet structure and Monte Carlo style updates, MemRL enables agents to self-evolve and differentiate high-utility strategies from semantic noise without weight updates. Extensive evaluations confirm MemRL significantly outperforms baselines in both runtime adaptation and generalization. In a future where static training data becomes scarce, the interactive experiences generated by agents throughout their life cycle will become a new, vital source of knowledge. We hope this paradigm paves the way for building stable, continuously learning agents that efficiently adapt from interaction.

## Impact Statement