MemRL: Self-Evolving Agents via Runtime Reinforcement Learning on Episodic Memory — part 4/6
Cleaned-text code points [46815, 62688). Bibliography omitted here; source.md includes it.
To resolve this, we formulate the problem as maximizing a global variational objective 𝒥 ( μ , Q ) \mathcal{J}(\mu,Q) . This objective serves as a tractable lower bound for the global expected return defined in Eq. 19 , balanced by a semantic trust region: 𝒥 ( μ , Q ) = 𝔼 s ∼ 𝒟 [ ∑ m ∈ 𝒮 ( s ) μ ( m | s ) Q ( s , m ) ⏟ Expected Utility ≈ 𝔼 [ Q t ( m ) ] − 1 β D KL ( μ ( ⋅ | s ) ∥ π sim ( ⋅ | s ) ) ⏟ Semantic Trust Region ] \mathcal{J}(\mu,Q)=\mathbb{E}_{s\sim\mathcal{D}}\left[\underbrace{\sum_{m\in\mathcal{S}(s)}\mu(m|s)Q(s,m)}_{\text{Expected Utility }\approx\mathbb{E}[Q_{t}(m)]}-\frac{1}{\beta}\underbrace{D_{\text{KL}}\Big(\mu(\cdot|s)\big\|\pi_{\text{sim}}(\cdot|s)\Big)}_{\text{Semantic Trust Region}}\right] (20) Here, the expectation is taken over the state distribution 𝒟 \mathcal{D} . The first term directly corresponds to the expected utility 𝔼 [ Q t ( m ) ] \mathbb{E}[Q_{t}(m)] we aim to converge, while π sim \pi_{\text{sim}} represents the fixed semantic prior (derived from Phase-A). The KL-divergence term acts as a regularizer crucial for two reasons: 1. Trust Region: It constrains the policy to the support set 𝒮 \mathcal{S} , preventing the agent from retrieving high-Q but semantically irrelevant memories (out-of-distribution errors).
2. Regularization: It stabilizes the learning dynamics during the “cold start” phase when Q-estimates are noisy.
#### A.4.3 Optimization via Generalized Expectation-Maximization (GEM)
We treat the optimization of 𝒥 \mathcal{J} as a GEM process, alternating between policy improvement and value evaluation:
##### E-Step (Policy Optimization).
We assume the utility estimates Q ( s , m ) Q(s,m) are fixed and seek the optimal retrieval policy μ ∗ \mu^{*} that maximizes the global variational objective 𝒥 ( μ , Q ) \mathcal{J}(\mu,Q) . Since the expectation is taken over the state distribution 𝒟 \mathcal{D} , we can maximize the objective for each state s s pointwise. The optimization problem for a specific state s s is:
max μ ( ⋅ | s ) [ ∑ m ∈ 𝒮 ( s ) μ ( m | s ) Q ( s , m ) − 1 β D KL ( μ ( ⋅ | s ) ∥ π sim ( ⋅ | s ) ) ] \max_{\mu(\cdot|s)}\left[\sum_{m\in\mathcal{S}(s)}\mu(m|s)Q(s,m)-\frac{1}{\beta}D_{\text{KL}}\Big(\mu(\cdot|s)\big\|\pi_{\text{sim}}(\cdot|s)\Big)\right] (21) subject to the probability simplex constraint ∑ m ∈ 𝒮 ( s ) μ ( m | s ) = 1 \sum_{m\in\mathcal{S}(s)}\mu(m|s)=1 .
Expanding the KL-divergence term, the objective function becomes: ℒ ( μ ) = ∑ m ∈ 𝒮 ( s ) μ ( m | s ) ( Q ( s , m ) + 1 β log π sim ( m | s ) μ ( m | s ) ) . \mathcal{L}(\mu)=\sum_{m\in\mathcal{S}(s)}\mu(m|s)\left(Q(s,m)+\frac{1}{\beta}\log\frac{\pi_{\text{sim}}(m|s)}{\mu(m|s)}\right). (22)
To enforce the normalization constraint, we introduce the Lagrange multiplier λ \lambda and construct the Lagrangian: L ( μ , λ ) = ∑ m ∈ 𝒮 ( s ) μ ( m | s ) ( Q ( s , m ) + 1 β log π sim ( m | s ) μ ( m | s ) ) + λ ( 1 − ∑ m ∈ 𝒮 ( s ) μ ( m | s ) ) . L(\mu,\lambda)=\sum_{m\in\mathcal{S}(s)}\mu(m|s)\left(Q(s,m)+\frac{1}{\beta}\log\frac{\pi_{\text{sim}}(m|s)}{\mu(m|s)}\right)+\lambda\left(1-\sum_{m\in\mathcal{S}(s)}\mu(m|s)\right).
Taking the derivative with respect to μ ( m | s ) \mu(m|s) and setting it to zero: ∂ L ∂ μ ( m | s ) \displaystyle\frac{\partial L}{\partial\mu(m|s)} = Q ( s , m ) + 1 β ( log π sim ( m | s ) μ ( m | s ) + μ ( m | s ) ⋅ μ ( m | s ) π sim ( m | s ) ⋅ − π sim ( m | s ) μ ( m | s ) 2 ) − λ \displaystyle=Q(s,m)+\frac{1}{\beta}\left(\log\frac{\pi_{\text{sim}}(m|s)}{\mu(m|s)}+\mu(m|s)\cdot\frac{\mu(m|s)}{\pi_{\text{sim}}(m|s)}\cdot\frac{-\pi_{\text{sim}}(m|s)}{\mu(m|s)^{2}}\right)-\lambda = Q ( s , m ) + 1 β ( log π sim ( m | s ) μ ( m | s ) − 1 ) − λ = 0 . \displaystyle=Q(s,m)+\frac{1}{\beta}\left(\log\frac{\pi_{\text{sim}}(m|s)}{\mu(m|s)}-1\right)-\lambda=0.
Rearranging terms to solve for μ ( m | s ) \mu(m|s) : log π sim ( m | s ) μ ( m | s ) \displaystyle\log\frac{\pi_{\text{sim}}(m|s)}{\mu(m|s)} = β λ − β Q ( s , m ) + 1 \displaystyle=\beta\lambda-\beta Q(s,m)+1 μ ( m | s ) π sim ( m | s ) \displaystyle\frac{\mu(m|s)}{\pi_{\text{sim}}(m|s)} = exp ( β Q ( s , m ) − ( β λ + 1 ) ) \displaystyle=\exp\left(\beta Q(s,m)-(\beta\lambda+1)\right) μ ( m | s ) \displaystyle\mu(m|s) = π sim ( m | s ) exp ( β Q ( s , m ) ) ⋅ exp ( − ( β λ + 1 ) ) . \displaystyle=\pi_{\text{sim}}(m|s)\exp(\beta Q(s,m))\cdot\exp(-(\beta\lambda+1)).
Since exp ( − ( β λ + 1 ) ) \exp(-(\beta\lambda+1)) is independent of m m , it acts as a normalization constant 1 / Z ( s ) 1/Z(s) . Thus, we recover the closed-form Boltzmann distribution used in our Phase-B retrieval: μ ∗ ( m | s ) = π sim ( m | s ) exp ( β Q ( s , m ) ) Z ( s ) ∝ π sim ( m | s ) exp ( β Q ( s , m ) ) . \mu^{*}(m|s)=\frac{\pi_{\text{sim}}(m|s)\exp(\beta Q(s,m))}{Z(s)}\propto\pi_{\text{sim}}(m|s)\exp(\beta Q(s,m)). This derivation theoretically justifies our heuristic scoring function: the optimal retrieval policy naturally balances the semantic prior π sim \pi_{\text{sim}} and the learned utility Q Q . By taking the logarithm, we recover the specific scoring function used in our Phase-B Retrieval (Eq. 7 ): log μ ∗ ( m | s ) ∝ log π sim ( m | s ) ⏟ ≈ sim ( s , m ) + β Q t ( s , m ) \log\mu^{*}(m|s)\propto\underbrace{\log\pi_{\text{sim}}(m|s)}_{\approx\text{sim}(s,m)}+\beta Q_{t}(s,m) This proves that our heuristic combination of similarity and Q-value is mathematically equivalent to the optimal policy under the variational objective.
##### M-Step (Policy Evaluation via Error Minimization).
While the E-step improves the policy based on current estimates, the M-step ensures these estimates are grounded in reality. Fixing the policy μ t + 1 \mu_{t+1} , our goal is to align the variational parameter Q Q with the true environmental returns. We formulate this as minimizing the Mean Squared Error (MSE) between the estimated utility and the observed reward target y = r y=r (in our Monte Carlo style modeling): min Q ℒ ( Q ) = 𝔼 τ ∼ μ t + 1 [ 1 2 ( y − Q ( s , m ) ) 2 ] \min_{Q}\mathcal{L}(Q)=\mathbb{E}_{\tau\sim\mu_{t+1}}\left[\frac{1}{2}\left(y-Q(s,m)\right)^{2}\right] (23) Minimizing this error is critical because it tightens the variational bound: it ensures that the expectation term 𝔼 [ Q ] \mathbb{E}[Q] in the global objective 𝒥 \mathcal{J} (Eq. 20 ) converges to the true expected return 𝔼 [ r ] \mathbb{E}[r] . The update rule used in our approach (Eq. 4 ) corresponds exactly to a Stochastic Gradient Descent (SGD) step on this objective: Q t + 1 ( s , m ) ← Q t ( s , m ) − α ∇ Q ℒ ( Q ) = Q t ( s , m ) + α ( y − Q t ( s , m ) ) Q_{t+1}(s,m)\leftarrow Q_{t}(s,m)-\alpha\nabla_{Q}\mathcal{L}(Q)=Q_{t}(s,m)+\alpha(y-Q_{t}(s,m)) By iteratively minimizing ℒ ( Q ) \mathcal{L}(Q) , the M-step propagates the environmental feedback into the utility estimates, ensuring that the subsequent E-step optimization occurs on a reliable value landscape.
#### A.4.4 Proof of Convergence
By the Monotonic Improvement Theorem of GEM ( Neal and Hinton, 1998 ) , the sequence ( μ t , Q t ) (\mu_{t},Q_{t}) is guaranteed to converge to a stationary point ( μ ∗ , Q ∗ ) (\mu^{*},Q^{*}) . At stationarity, the policy stabilizes ( μ t + 1 ≈ μ t \mu_{t+1}\approx\mu_{t} ), which implies that the inverse retrieval probability Pr ( s | m ) \Pr(s|m) becomes time-invariant : Pr ( s | m ) = μ ∗ ( m | s ) Pr ( s ) ∑ s ′ μ ∗ ( m | s ′ ) Pr ( s ′ ) \Pr(s|m)=\frac{\mu^{*}(m|s)\Pr(s)}{\sum_{s^{\prime}}\mu^{*}(m|s^{\prime})\Pr(s^{\prime})} Consequently, the “Retrieve-Dependent” term in Eq. 19 is anchored. With a fixed data distribution, the Q t ( m ) Q_{t}(m) converges to the unique fixed point: lim t → ∞ Q t ( m ) → 𝔼 μ ∗ [ r | m ] \lim_{t\to\infty}Q_{t}(m)\to\mathbb{E}_{\mu^{*}}[r|m] (24) Thus, our approach theoretically guarantees that the memory values converge to the true expected returns under the optimal retrieval policy.
## Appendix B Extended Analysis and Insights
### B.1 Detailed Analysis of Forgetting Dynamics
In the main text, we reported the mean forgetting rate to quantify the stability of our method. Here, we provide a detailed visual analysis of how the forgetting rate evolves throughout the learning process on the HLE benchmark.
As illustrated in Figure 9 , MemRL demonstrates superior stability compared to MemP. Specifically: • Stability vs. Plasticity: While MemP shows a gradual upward trend in forgetting rate as the number of episodes increases, MemRL maintains a consistently low rate. This indicates that our dual-retrieval mechanism effectively balances the acquisition of new strategies without overwriting stable, high-utility memories.
• Impact of Filtering: The ablation curve (denoted as w/o Norm & SimGate ) exhibits significant higher overall forgetting rate ( 0.073 0.073 mean). The visible spikes in the curve suggest that without z-score normalization and similarity gating, the agent frequently retrieves and reinforces “noisy” strategies that work for specific instances but degrade general performance on previously mastered tasks.
### B.2 MemRL as a Trajectory Verifier.
Table 4 reveals a correlation between task structural complexity and performance gain. The gains are most profound in multi-step sequential tasks (e.g., ALFWorld + 6.2 % +6.2\% Points(pp)) compared to single-turn tasks (e.g., BigCodeBench + 2.5 % +2.5\% pp). In sequential tasks, a retrieved memory must be valid for the entire trajectory. Standard semantic retrieval often fetches memories that match the initial instruction but fail in later steps. By propagating the final reward backward to the memory utility Q Q , MemRL effectively learns to verify the whole trajectory , filtering out brittle policies that look correct only on the surface.
This analysis indicates that MemRL transcends the role of a simple retrieval enhancer to function as a Trajectory Verifier . Its value is maximized in tasks with complex temporal dependencies, where it learns to select memories that ensure the structural integrity of the entire interaction process.
### B.3 Impact of Task Similarity on Memory Efficacy
To understand the underlying conditions where MemRL thrives, we analyze the correlation between the intra-dataset semantic similarity ( Sim i n t r a \text{Sim}_{intra} ) and the absolute performance gain provided by our method ( Δ = Success Rate MemRL − Success Rate NoMem \Delta=\text{Success Rate}_{\text{MemRL}}-\text{Success Rate}_{\text{NoMem}} ).
As illustrated in Figure 10 , we analyze the correlation between intra-dataset semantic similarity and the absolute performance gain ( Δ \Delta ) provided by MemRL . The linear regression trend reveals a general positive correlation: environments with higher structural repetition allow the agent to retrieve and reuse optimal policies more effectively. At the upper extreme, ALFWorld (similarity 0.518 0.518 ) acts as a strong anchor point for this trend, exhibiting the highest repetition and a corresponding maximum performance boost ( Δ = + 0.172 \Delta=+0.172 ). This confirms that for highly repetitive procedural tasks, memory serves as an effective shortcut to optimal trajectories. Following the regression line, benchmarks with moderate similarity—such as Lifelong-OS ( 0.390 0.390 ) and BigCodeBench ( 0.308 0.308 )—cluster in the middle region, showing steady improvements ( Δ ≈ + 0.10 ∼ + 0.11 \Delta\approx+0.10\sim+0.11 ) where the agent successfully generalizes coding patterns or OS commands across related instructions.
The HLE Anomaly: Generalization vs. Memorization.
HLE presents a unique outlier. Despite having the lowest similarity ( 0.186 0.186 ) due to its diverse, multi-disciplinary nature, it exhibits a surprisingly high runtime gain ( 0.357 → 0.570 , Δ = + 0.213 0.357\rightarrow 0.570,\Delta=+0.213 ). This gain operates on a different mechanism than ALFWorld. In high-similarity benchmarks, MemRL succeeds via Positive Transfer —generalizing shared patterns to new instances. In contrast, the gain in HLE stems from Runtime Memorization . Since HLE questions are distinct and domain-specific, the agent relies on the Runtime Learning phase to “memorize” specific solutions to difficult problems through repeated exposure. This distinction highlights MemRL ’s versatility: it supports both pattern generalization in structured domains and specific knowledge acquisition in diverse domains.
## Appendix C Advanced Capabilities: Transfer and Merging
### C.1 Cross-Model Memory Transferability
We investigate whether the procedural knowledge captured by MemRL is specific to the training policy or if it generalizes across different architectures. To test this, we take a memory bank fully trained for 10 epochs on the HLE benchmark using our strongest agent, Gemini-3-pro , and directly transfer it—without any fine-tuning—to three distinct inference models: Qwen3-235B , GPT-5.2(High) , and Gemini-3-flash .
As summarized in Table 5 , the transferred memory yields substantial zero-shot performance gains across all models. Notably, smaller or distilled models experience the largest relative improvements; for instance, Qwen3-235B improves by over 3 × 3\times ( 0.150 → 0.531 0.150\rightarrow 0.531 ) and Gemini-3-flash nearly doubles its success rate ( 0.347 → 0.583 0.347\rightarrow 0.583 ). Even GPT-5.2(High) , a highly capable reasoning model, sees a significant boost ( 0.354 → 0.571 0.354\rightarrow 0.571 ).
These results suggest that MemRL captures model-agnostic problem-solving patterns—such as efficient code skeletons and reasoning templates—rather than model-specific artifacts. This effectively allows the memory bank to function as a portable knowledge base, enabling weaker models to “inherit” the capabilities of a stronger teacher model through simple retrieval.
### C.2 Multi-Task Memory Merging and Interference Analysis
To evaluate the composability and robustness of MemRL in multi-task scenarios, we conducted a memory merging experiment. Specifically, we aggregated the finalized memory banks learned from the last epoch of two distinct domains within the Lifelong Agent Bench: Operating System Control ( M O S M_{OS} ) and Database Management ( M D B M_{DB} ). The agent was then evaluated on each respective benchmark using this unified, heterogeneous memory bank ( M U n i f i e d = M O S ∪ M D B M_{Unified}=M_{OS}\cup M_{DB} ), without any further training or fine-tuning.
As presented in Table 6 , the results demonstrate that merging memories introduces negligible interference. The performance on the DB Task remains identical ( 0.960 0.960 ), while the OS Task exhibits only a marginal fluctuation ( 0.788 → 0.784 0.788\rightarrow 0.784 ). This robustness is intrinsic to our Two-Phase Retrieval mechanism. Since the semantic spaces of OS commands and SQL queries are largely orthogonal, the Phase-A similarity filter effectively acts as a semantic gate, automatically excluding irrelevant cross-task memories before they enter the value-based ranking stage. This confirms that MemRL supports modular memory composition, allowing agents to scale capabilities by simply merging memory modules without suffering from negative transfer or catastrophic interference.
## Appendix D Baseline and Benchmark Details
To ensure a rigorous evaluation, we compare MemRL against a diverse set of baselines ranging from simple sampling strategies to advanced agentic memory systems. All baselines are evaluated under a unified frozen-backbone setting to isolate the contribution of the memory and retrieval mechanisms.
### D.1 Baselines
We categorize the baselines into three groups based on their interaction with memory and environment:
##### I. Test-Time Scaling Strategy