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

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

This paper presents MemRL , a value-reinforced memory retrieval mechanism designed to enhance the long-term reasoning capabilities of LLM Agents. From a broader perspective, our work contributes to the development of more efficient and reliable autonomous systems. By optimizing the memory retrieval process, MemRL reduces the computational overhead of large-scale agent deployments, potentially lowering the environmental impact of AI infrastructure. Furthermore, as LLM agents become more integrated into daily workflows, research into robust memory mechanisms helps ensure these systems remain grounded and consistent in their actions. We do not foresee any immediate negative social consequences specific to this algorithmic advancement, though we acknowledge that all autonomous systems should be deployed with appropriate human oversight to mitigate broader risks associated with AI decision-making.

## Appendix A Theoretical Analysis and Proofs

### A.1 Stability Analysis

We analyze the stability of MemRL from a reinforcement learning perspective, focusing on the convergence behavior of the utility estimates stored in memory. MemRL performs non-parametric runtime learning using a constant-step-size update. We show that under mild and realistic assumptions, the learned utility values converge in expectation to stable estimates of memory effectiveness, with bounded variance.

##### Setup.

At each time step t t , the agent observes an intent state s t s_{t} , retrieves a memory item m t ∈ ℳ t m_{t}\in\mathcal{M}_{t} , generates an output a t a_{t} , and receives a scalar reward r t ∈ [ − 1 , 1 ] r_{t}\in[-1,1] indicating task success or failure. The generation policy follows the decomposition defined in Eq. 1 , where μ \mu denotes the retrieval policy and p LLM p_{\mathrm{LLM}} is a frozen inference policy.

For each retrieved memory, MemRL updates its utility using the exponential moving average rule as formulated in Eq. 4 , with learning rate α ∈ ( 0 , 1 ] \alpha\in(0,1] . For clarity in this analysis, we consider a fixed state–memory pair ( s , m ) (s,m) and write Q t ≡ Q t ​ ( s , m ) Q_{t}\equiv Q_{t}(s,m) .

##### Stationary Reward Assumption.

We analyze the learning process on a fixed dataset and posit two key conditions that ensure the stability of the environment: 1. Frozen Inference Policy. The parameters of p LLM ​ ( y | s , m ) p_{\mathrm{LLM}}(y|s,m) and the evaluator’s criteria are fixed.

2. Fixed Task Distribution. Tasks s s are drawn from a stationary distribution over a fixed dataset.

These assumptions guarantee that the learning target is well-defined: the expected reward for any specific task-memory pair is time-invariant. Thus, we have:

where the expectation is taken over the stochastic rewards resulting from the Inference Policy p L ​ L ​ M p_{LLM} distribution.

##### Expected Convergence of Utility Estimates.

We now state the main stability result.

###### Theorem A.1 .

Let { Q t } \{Q_{t}\} be updated according to the rule in Eq. 4 with constant step size α ∈ ( 0 , 1 ] \alpha\in(0,1] . If Eq. 10 holds and the pair ( s , m ) (s,m) is updated infinitely often, then: lim t → ∞ 𝔼 [ Q t ] = 𝔼 [ r t | s t = s , m t = m ] = β ( s , m ) . \lim_{t\to\infty}\mathbb{E}[Q_{t}]=\mathbb{E}[r_{t}|s_{t}=s,\;m_{t}=m]=\beta(s,m). (11) Moreover, the convergence rate is exponential ( Sutton and Barto, 2018 ) : 𝔼 ⁡ [ Q t ] − β ⁡ ( s , m ) = ( 1 − α ) t ​ ( Q 0 − β ⁡ ( s , m ) ) . \mathbb{E}[Q_{t}]-\beta(s,m)=(1-\alpha)^{t}\big(Q_{0}-\beta(s,m)\big). (12)

##### Proof.

Define the estimation error e t ≜ Q t − β ⁡ ( s , m ) e_{t}\triangleq Q_{t}-\beta(s,m) . Based on the update rule in Eq. 4 , the error recurrence relation is: e t + 1 = ( 1 − α ) ​ e t + α ⁡ ( r t − β ⁡ ( s , m ) ) . e_{t+1}=(1-\alpha)e_{t}+\alpha\big(r_{t}-\beta(s,m)\big). Taking conditional expectation given the history ℱ t \mathcal{F}_{t} and using Eq. 10 , we obtain: 𝔼 ⁡ [ e t + 1 | ℱ t ] = ( 1 − α ) ​ e t . \mathbb{E}[e_{t+1}|\mathcal{F}_{t}]=(1-\alpha)e_{t}. Taking full expectation yields: 𝔼 ⁡ [ e t + 1 ] = ( 1 − α ) ​ 𝔼 ​ [ e t ] . \mathbb{E}[e_{t+1}]=(1-\alpha)\mathbb{E}[e_{t}]. Iterating the recursion gives 𝔼 ⁡ [ e t ] = ( 1 − α ) t ​ e 0 \mathbb{E}[e_{t}]=(1-\alpha)^{t}e_{0} , which converges to zero as t → ∞ t\to\infty . □ \square

We provide the detailed derivation of the convergence proof in Appendix A.2 .

##### Bounded Variance and Stability.

If the reward variance Var ⁡ ( r t | s , m ) < ∞ \mathrm{Var}(r_{t}|s,m)<\infty , then the variance of Q t Q_{t} remains bounded: lim sup t → ∞ Var ⁡ ( Q t ) ≤ α 2 − α ​ Var ​ ( r t | s , m ) . \limsup_{t\to\infty}\mathrm{Var}(Q_{t})\leq\frac{\alpha}{2-\alpha}\,\mathrm{Var}(r_{t}|s,m). (13) Thus, constant-step-size updates do not induce unbounded oscillations; instead, they yield stable utility estimates that track expected memory effectiveness while filtering high-frequency noise. We explicitly derive the variance bounds to demonstrate the global stability of the estimator under task clustering in Appendix A.3 .

##### Global Stability via EM Convergence.

The stability of the local estimate (Theorem A.1 ) extends to the global memory utility Q ⁡ ( m ) Q(m) . By the linearity of expectation, Q ⁡ ( m ) Q(m) acts as a Monte Carlo integrator striving to converge to:

lim t → ∞ 𝔼 ⁡ [ Q t ​ ( m ) ] = 𝔼 ⁡ [ r | m ] = ∑ s ∈ 𝒮 ⁡ ( m ) 𝔼 [ r | s , m ] ⏟ Stationary ​ Pr ⁡ ( s | m ) ⏟ Retrieve-Dependent . \lim_{t\to\infty}\mathbb{E}[Q_{t}(m)]=\mathbb{E}[r|m]=\sum_{s\in\mathcal{S}(m)}\underbrace{\mathbb{E}[r|s,m]}_{\text{Stationary}}\underbrace{\Pr(s|m)}_{\text{Retrieve-Dependent}}. (14)

where 𝒮 ⁡ ( m ) ≜ { s ∈ 𝒮 | sim ​ ( s , z m ) ≥ τ A } \mathcal{S}(m)\triangleq\{s\in\mathcal{S}|\text{sim}(s,z_{m})\geq\tau_{A}\} denotes the effective support set for memory m m , comprising all task intents s s sufficiently similar to the memory’s intent embedding z m z_{m} to satisfy the Phase-A retrieval criterion.

A theoretical challenge arises here: the weighting term Pr ⁡ ( s | m ) \Pr(s|m) is a latent variable governed by the retrieval policy μ ⁡ ( m | s ; ℳ ) \mu(m|s;\mathcal{M}) , which itself shifts as Q Q -values evolve. To prove convergence despite this dependency, we analyze MemRL as a Generalized Expectation-Maximization (GEM) process ( Dempster et al., 1977 ; Neal and Hinton, 1998 ) . From a variational perspective, the system performs coordinate ascent on a global objective function 𝒥 ⁡ ( Q , μ ) \mathcal{J}(Q,\mu) (the variational lower bound of expected reward): (i) E-Step (Policy Improvement): The Phase-B ranking updates the retrieval policy μ \mu to align with current estimates, monotonically increasing 𝒥 \mathcal{J} with respect to μ \mu ; (ii) M-Step (Value Update): The utility update (Eq. 4 ) increases 𝒥 \mathcal{J} with respect to Q Q . By the Monotonic Improvement Theorem ( Neal and Hinton, 1998 ) , this alternating optimization guarantees that the system converges to a stationary point where the retrieve policy stabilizes ( μ t + 1 ≈ μ t \mu_{t+1}\approx\mu_{t} ). Consequently, the induced distribution Pr ⁡ ( s | m ) \Pr(s|m) becomes time-invariant, ensuring that Eq. 14 holds and effectively preventing catastrophic forgetting by anchoring updates to a stable policy. More details can be found in Appendix A.4 .

### A.2 Proof of Theorem A.1 : Convergence of EMA Estimation

We aim to prove that for a fixed task-memory pair ( s , m ) (s,m) with a stationary reward distribution, the Q-value estimate Q t ​ ( s , m ) Q_{t}(s,m) converges in expectation to the true mean reward β ⁡ ( s , m ) \beta(s,m) .

##### Assumptions.

1. Stationary Reward. The reward r t r_{t} at step t t is drawn from a distribution induced by the stochastic action generation a ∼ p L ​ L ​ M ​ ( a t | s t , m ) a\sim p_{LLM}(a_{t}|s_{t},m) , with a constant mean β ( s , m ) = 𝔼 [ r t | s , m ] \beta(s,m)=\mathbb{E}[r_{t}|s,m] and finite variance σ 2 \sigma^{2} .

2. Update Rule. The utility is updated via the linear EMA rule with learning rate α ∈ ( 0 , 1 ) \alpha\in(0,1) : Q t + 1 = ( 1 − α ) ​ Q t + α ​ r t . Q_{t+1}=(1-\alpha)Q_{t}+\alpha r_{t}.

##### Derivation of Error Dynamics.

Let e t ≜ Q t − β ⁡ ( s , m ) e_{t}\triangleq Q_{t}-\beta(s,m) be the estimation error at time step t t . Substituting Q t = e t + β ⁡ ( s , m ) Q_{t}=e_{t}+\beta(s,m) into the update rule:

e t + 1 + β ⁡ ( s , m ) \displaystyle e_{t+1}+\beta(s,m) = ( 1 − α ) ​ ( e t + β ⁡ ( s , m ) ) + α ​ r t \displaystyle=(1-\alpha)(e_{t}+\beta(s,m))+\alpha r_{t} e t + 1 \displaystyle e_{t+1} = ( 1 − α ) ​ e t + ( 1 − α ) ​ β ​ ( s , m ) + α ​ r t − β ⁡ ( s , m ) \displaystyle=(1-\alpha)e_{t}+(1-\alpha)\beta(s,m)+\alpha r_{t}-\beta(s,m) e t + 1 \displaystyle e_{t+1} = ( 1 − α ) ​ e t + β ⁡ ( s , m ) − α ​ β ​ ( s , m ) − β ⁡ ( s , m ) + α ​ r t \displaystyle=(1-\alpha)e_{t}+\beta(s,m)-\alpha\beta(s,m)-\beta(s,m)+\alpha r_{t} e t + 1 \displaystyle e_{t+1} = ( 1 − α ) ​ e t + α ⁡ ( r t − β ⁡ ( s , m ) ) . \displaystyle=(1-\alpha)e_{t}+\alpha(r_{t}-\beta(s,m)). (15)

##### Convergence Analysis.

We define ℱ t \mathcal{F}_{t} as the filtration (history) up to time t t . Since the reward r t r_{t} depends on the action a t a_{t} sampled subsequently from the frozen LLM, taking the conditional expectation of Eq. 15 given ℱ t \mathcal{F}_{t} :

𝔼 ⁡ [ e t + 1 | ℱ t ] = ( 1 − α ) ​ e t + α ⁡ ( 𝔼 ⁡ [ r t | ℱ t ] ⏟ β ⁡ ( s , m ) − β ⁡ ( s , m ) ) = ( 1 − α ) ​ e t . \mathbb{E}[e_{t+1}|\mathcal{F}_{t}]=(1-\alpha)e_{t}+\alpha(\underbrace{\mathbb{E}[r_{t}|\mathcal{F}_{t}]}_{\beta(s,m)}-\beta(s,m))=(1-\alpha)e_{t}.

By the Law of Iterated Expectations, taking the full expectation yields: 𝔼 ⁡ [ e t + 1 ] = 𝔼 ⁡ [ 𝔼 ⁡ [ e t + 1 | ℱ t ] ] = ( 1 − α ) ​ 𝔼 ​ [ e t ] . \mathbb{E}[e_{t+1}]=\mathbb{E}[\mathbb{E}[e_{t+1}|\mathcal{F}_{t}]]=(1-\alpha)\mathbb{E}[e_{t}].

Iterating this recurrence relation from t = 0 t=0 : 𝔼 ⁡ [ e t ] = ( 1 − α ) t ​ 𝔼 ​ [ e 0 ] . \mathbb{E}[e_{t}]=(1-\alpha)^{t}\mathbb{E}[e_{0}].

Since 0 < α < 1 0<\alpha<1 , we have | 1 − α | < 1 |1-\alpha|<1 . Consequently: lim t → ∞ 𝔼 ⁡ [ e t ] = 𝔼 ⁡ [ e 0 ] ⋅ lim t → ∞ ( 1 − α ) t = 0 . \lim_{t\to\infty}\mathbb{E}[e_{t}]=\mathbb{E}[e_{0}]\cdot\lim_{t\to\infty}(1-\alpha)^{t}=0. (16)

This proves that the estimator is unbiased in the limit, i.e., lim t → ∞ 𝔼 ⁡ [ Q t ] = β ⁡ ( s , m ) \lim_{t\to\infty}\mathbb{E}[Q_{t}]=\beta(s,m) . □ \square

### A.3 Bounded Variance and Global Stability

In this section, we provide the formal derivation for the variance bound of the estimator Q t Q_{t} . We explicitly derive the finite-time variance formula via recursive unrolling and prove its asymptotic convergence, demonstrating how Phase-A clustering contributes to global stability.

##### Derivation of the Variance Bound.

Let σ 2 ≜ Var ⁡ ( r t | s , m ) \sigma^{2}\triangleq\mathrm{Var}(r_{t}|s,m) be the variance of the reward signal, assumed to be finite. The EMA update rule is given by: Q t + 1 = ( 1 − α ) ​ Q t + α ​ r t . Q_{t+1}=(1-\alpha)Q_{t}+\alpha r_{t}. Since the reward r t r_{t} (current noise) is statistically independent of the current estimate Q t Q_{t} (which is determined by history ℱ t − 1 \mathcal{F}_{t-1} ), the variance of the sum is the sum of the variances: Var ⁡ ( Q t + 1 ) \displaystyle\mathrm{Var}(Q_{t+1}) = Var ⁡ ( ( 1 − α ) ​ Q t ) + Var ⁡ ( α ​ r t ) \displaystyle=\mathrm{Var}((1-\alpha)Q_{t})+\mathrm{Var}(\alpha r_{t}) = ( 1 − α ) 2 ​ Var ​ ( Q t ) + α 2 ​ σ 2 . \displaystyle=(1-\alpha)^{2}\mathrm{Var}(Q_{t})+\alpha^{2}\sigma^{2}. Let v t ≜ Var ⁡ ( Q t ) v_{t}\triangleq\mathrm{Var}(Q_{t}) . We obtain a linear recurrence relation v t + 1 = ( 1 − α ) 2 ​ v t + α 2 ​ σ 2 v_{t+1}=(1-\alpha)^{2}v_{t}+\alpha^{2}\sigma^{2} .

##### Recursive Unrolling.

To solve for v t v_{t} , we expand the recurrence relation backward from step t t : v t \displaystyle v_{t} = ( 1 − α ) 2 ​ v t − 1 + α 2 ​ σ 2 \displaystyle=(1-\alpha)^{2}v_{t-1}+\alpha^{2}\sigma^{2} = ( 1 − α ) 2 ​ [ ( 1 − α ) 2 ​ v t − 2 + α 2 ​ σ 2 ] + α 2 ​ σ 2 \displaystyle=(1-\alpha)^{2}\left[(1-\alpha)^{2}v_{t-2}+\alpha^{2}\sigma^{2}\right]+\alpha^{2}\sigma^{2} = ( 1 − α ) 4 ​ v t − 2 + α 2 ​ σ 2 ​ [ 1 + ( 1 − α ) 2 ] \displaystyle=(1-\alpha)^{4}v_{t-2}+\alpha^{2}\sigma^{2}\left[1+(1-\alpha)^{2}\right] ⋮ \displaystyle\quad\vdots = ( 1 − α ) 2 ​ t ​ v 0 + α 2 ​ σ 2 ​ ∑ k = 0 t − 1 ( ( 1 − α ) 2 ) k . \displaystyle=(1-\alpha)^{2t}v_{0}+\alpha^{2}\sigma^{2}\sum_{k=0}^{t-1}\left((1-\alpha)^{2}\right)^{k}. (17) Eq. 17 explicitly shows that the variance at time t t consists of two components: the decayed initial variance (first term) and the accumulated noise variance (second term).

##### Asymptotic Convergence.

As t → ∞ t\to\infty , since the learning rate α ∈ ( 0 , 1 ) \alpha\in(0,1) , the term ( 1 − α ) 2 ​ t (1-\alpha)^{2t} vanishes. The summation term is a geometric series ∑ k = 0 ∞ r k = 1 1 − r \sum_{k=0}^{\infty}r^{k}=\frac{1}{1-r} with ratio r = ( 1 − α ) 2 r=(1-\alpha)^{2} . Thus: lim t → ∞ v t = α 2 ​ σ 2 ⋅ 1 1 − ( 1 − α ) 2 . \lim_{t\to\infty}v_{t}=\alpha^{2}\sigma^{2}\cdot\frac{1}{1-(1-\alpha)^{2}}. Evaluating the denominator: 1 − ( 1 − α ) 2 = 1 − ( 1 − 2 ​ α + α 2 ) = 2 ​ α − α 2 = α ⁡ ( 2 − α ) . 1-(1-\alpha)^{2}=1-(1-2\alpha+\alpha^{2})=2\alpha-\alpha^{2}=\alpha(2-\alpha). Substituting this back yields the tight variance bound: lim sup t → ∞ Var ⁡ ( Q t ) = α 2 ​ σ 2 α ⁡ ( 2 − α ) = α 2 − α ​ σ 2 . \limsup_{t\to\infty}\mathrm{Var}(Q_{t})=\frac{\alpha^{2}\sigma^{2}}{\alpha(2-\alpha)}=\frac{\alpha}{2-\alpha}\sigma^{2}. (18)

##### Connection to Phase-A Clustering.

This result provides the theoretical justification for the stability of MemRL . While tasks within a memory cluster 𝒮 ⁡ ( m ) ≜ { s | sim ​ ( s , z m ) > τ A } \mathcal{S}(m)\triangleq\{s|\text{sim}(s,z_{m})>\tau_{A}\} may vary, the Smoothness Assumption implies their rewards are drawn from a distribution with bounded variance σ 𝒮 ⁡ ( m ) 2 \sigma^{2}_{\mathcal{S}(m)} . The derived bound α 2 − α ​ σ 𝒮 ⁡ ( m ) 2 \frac{\alpha}{2-\alpha}\sigma^{2}_{\mathcal{S}(m)} guarantees that the memory utility Q ⁡ ( m ) Q(m) will not diverge but will instead oscillate within a controlled range around the true expected utility. This mechanism effectively filters out high-frequency noise from diverse task instances while retaining the stable generalized value.

### A.4 Convergence via Variational Inference

In this section, we provide a theoretical foundation for MemRL , demonstrating that our retrieval strategy and update rules guarantee the convergence of value estimation.

#### A.4.1 The Convergence Objective

Our ultimate goal is to ensure that the estimated utility Q ⁡ ( m ) Q(m) converges to the true expected return of memory m m . This target value is defined as: lim t → ∞ 𝔼 ⁡ [ Q t ​ ( m ) ] = 𝔼 ⁡ [ r | m ] = ∑ s ∈ 𝒮 ⁡ ( m ) 𝔼 [ r | s , m ] ⏟ Stationary ​ Pr ⁡ ( s | m ) ⏟ Retrieve-Dependent . \lim_{t\to\infty}\mathbb{E}[Q_{t}(m)]=\mathbb{E}[r|m]=\sum_{s\in\mathcal{S}(m)}\underbrace{\mathbb{E}[r|s,m]}_{\text{Stationary}}\underbrace{\Pr(s|m)}_{\text{Retrieve-Dependent}}. (19) The challenge lies in the term Pr ⁡ ( s | m ) \Pr(s|m) —the probability that a specific state s s triggers the retrieval of m m . This distribution depends on the retrieval policy μ t ​ ( m | s ) \mu_{t}(m|s) , which itself evolves during training, creating a circular dependency that threatens stability.

#### A.4.2 Variational Objective with Trust Region