acceptodds
Under review as a conference paper at ICLR 2027

Credit-Aware Memory Policy Optimization for Self-Evolving Black-Box Agents

16 views

Abstract

Self-evolving agents improve online by reusing experience accumulated in a memory of past user interactions. Adapting the agent itself from deployment feedback requires model parameters that the strongest API-served models do not expose, so the practical alternative learns per-memory utilities that decide which memories are retrieved for the current state. Such utilities, however, are updated with a shared trajectory-level return, which produces Memory Credit Leakage: because co-retrieved memories are indistinguishable to a single outcome signal, irrelevant and even harmful entries inherit the credit of the useful memories retrieved with them and accumulate spurious reinforcement as deployment lengthens. We argue that a memory deserves retrieval only if including it improves the return over excluding it, a contrast that no shared return can reveal. Therefore, we propose Credit-Aware Memory Policy Optimization (CMPO), an online framework that recovers this contrast from a single rollout by randomizing what the black-box agent sees rather than how it acts. CMPO exposes each memory through a stochastic gate with a recorded inclusion probability, so one rollout already contains both included and excluded memories, and reweighting the joint return by these probabilities yields a per-memory comparison that updates the gate, exposing useful memories more often and suppressing harmful ones. We prove that this credit is an unbiased estimator of the gate-local inclusion–exclusion return contrast and equals the derivative of the gate-local objective with respect to the inclusion probability. Across three benchmarks covering terminal interaction, embodied planning, and tool use, CMPO ranks first in 17 of 24 white-box and 20 of 24 black-box settings, sustaining accurate credit attribution over long-horizon deployment.

Primary area:
foundation or frontier models, including LLMs
Keywords:
self-evolution, agent, memory, LLM

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_VtZSOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper studies credit assignment for external-memory-based self-evolving agents. It identifies memory credit leakage, where co-retrieved memories share a trajectory-level return and irrelevant or harmful memories can therefore receive spurious positive credit. CMPO treats memory exposure as a stochastic Bernoulli policy and uses a propensity-corrected single-rollout estimator to update per-memory retrieval residuals. The paper proves unbiasedness for a gate-local inclusion–exclusion contrast and evaluates the method extensively on LifelongAgentBench, ALFWorld, and AppWorld with both white-box and black-box backbones.

Critical strengths

The paper identifies an important and practically relevant credit-assignment failure mode in online memory systems, clearly distinguishing the return observed when a memory is retrieved from the incremental value caused by including that memory. CMPO provides a practical black-box solution that requires no access to model parameters, gradients, or action log-probabilities, and avoids an additional counterfactual rollout for every memory decision. The empirical evaluation is unusually comprehensive, including multiple domains and backbones, a controlled credit-recovery study, online adaptation, component ablations, sensitivity analysis, paired uncertainty estimates, and held-out generalization.

Critical weaknesses

The theoretical credit is context-dependent, but the learned feedback residual is state-independent. Proposition 2 defines credit conditionally on the pre-gate history Ht,iH_{t,i}, so the same memory may be helpful in one context and harmful in another. CMPO does have a state-dependent semantic score et,ie_{t,i}, but the feedback learned from interaction outcomes is accumulated into a single persistent scalar residual ωi\omega_i for each memory and reused across states. Such a global learned correction cannot in general encode contextual credit whose sign changes, e.g., Δi(sA)>0\Delta_i(s_A)>0 but Δi(sB)<0\Delta_i(s_B)<0, unless the fixed semantic relevance term happens to separate those contexts appropriately. The current controlled credit-recovery experiment does not test this case: for each task instance it constructs one helpful, one irrelevant, and one harmful memory, removes the token budget, and uses independent Bernoulli(0.5) gates. I would therefore like to see a more non-ideal credit-assignment experiment that explicitly studies contextual sign flips, memory interactions, and/or budget-induced competition, together with a detailed analysis of both successful and failure cases. This is the main issue preventing a clear-accept recommendation. If the authors can convincingly address it, including with a well-designed non-ideal credit-assignment analysis, I would consider raising my rating.

A minor presentation issue is that claims such as “substantial and consistent” downstream gains should be softened or qualified, since several paired confidence intervals still include zero.

Questions for authors
  1. How does CMPO handle the same memory being helpful in one state but harmful in another, given that ωi\omega_i is a single state-independent scalar?

  2. Could the authors add a more non-ideal controlled credit-assignment experiment, e.g. contextual sign flips, memory interactions, or budget-induced competition, and analyze both where CMPO works and where it fails?

  3. Eq. (12) applies the estimator of ∂J/∂pt,i\partial J/\partial p_{t,i} directly to the logit residual ωi\omega_i, omitting the sigmoid factor pt,i(1−pt,i)p_{t,i}(1-p_{t,i}). Is this best interpreted as a preconditioned or natural-gradient-like update?

  4. Do the authors plan to release the implementation and evaluation code needed to reproduce the experiments?

5 comments

Dear Reviewer VtZS,

Thank you again for your constructive review. You noted that tests under non-ideal conditions would be the most important addition, so we highlight the new results:

  • Contextual sign flips. CMPO gains 9.6–16.4 points when the two contexts are separated in time. Under rapid switching, it stays within −3.8 to +1.3 points of the semantic-only control, and we analyze this failure case by context.
  • Budget competition. CMPO outperforms the control in all 12 configurations, with larger gains as the budget tightens.
  • Eq. (12) (Q3). The update is a gate-local inverse-Fisher preconditioning of the logit gradient.

Do these tests and the failure analysis address your main concern? We are happy to report any additional analysis before the discussion period closes.

Best regards, The Authors

Thank you for the additional experiments. I appreciate the context-level analysis, which helps clarify the limitations of the global residual.

I have two remaining questions:

  1. Context-specific credit estimation. Can the authors show whether CMPO can accurately estimate the memory's contribution separately in contexts A and B? In particular, I would like to see whether the estimated credits correctly capture the opposite signs of the memory's contribution in these two contexts, compared with the corresponding reference credits.

  2. Global vs. context-conditioned residuals. Can the authors provide a lightweight comparison between the current global residual and a context-conditioned residual? I would like to see whether a context-conditioned variant can better distinguish the two contexts, increasing the exposure of helpful memories in A while suppressing them in B, and whether this leads to better task performance in both contexts.

These results would help clarify whether the remaining limitation mainly comes from the global residual parameterization or whether there are also limitations in the credit estimation mechanism itself.

We thank the reviewer for the follow-up questions and address them in turn.

1. Context-specific credit estimation.

To test whether CMPO credits capture opposite signs under rapid switching, we compare them with contributions measured by additional paired rollouts under medium and high pressure (GPT-5.6-Luna, 30 LAB DB and 30 ALFWorld tasks, three paired seeds). For each pressure, task, context, and seed, we average the matured target-memory credits, assigning each to the context in which its gate was sampled. For the reference, we uniformly sample four saved states, two from each half of the gate history in that context, and run five inclusion/exclusion pairs from each with the original budget, task sequence, and continuation updates (H=3H=3, γ=1\gamma=1). Each half is weighted by its gate count to match the history distribution of the credits. MAE is the absolute difference between estimated and reference task-level averages, averaged over tasks. Entries are mean ± sample SD over three seeds.

DatasetPressureContextEstimatedReferenceMAE
LAB DBMediumA+0.28±0.09+0.20±0.070.15±0.07
LAB DBMediumB−0.15±0.17−0.18±0.050.11±0.08
LAB DBHighA+0.24±0.15+0.21±0.110.09±0.05
LAB DBHighB−0.27±0.20−0.18±0.090.14±0.13
ALFWorldMediumA+0.23±0.05+0.17±0.040.16±0.02
ALFWorldMediumB−0.26±0.08−0.23±0.040.08±0.06
ALFWorldHighA+0.19±0.12+0.16±0.080.17±0.08
ALFWorldHighB−0.20±0.03−0.22±0.060.12±0.04

CMPO recovers the opposite signs in both contexts. The mean credit matches the sign of the reference in all eight conditions and differs from it by only 0.02–0.09 return units under both pressures. The task-level MAE (0.08–0.17) is larger because each estimate averages noisy single-rollout credits and each reference uses only 20 pairs. This noise is why CMPO accumulates credits in a residual rather than acting on single estimates.

2. Global versus context-conditioned residuals.

To test whether this signal can be exploited, we compare global CMPO under high pressure with the fixed-zero control and a known-context variant. The variant replaces ωi\omega_i with two zero-initialized residuals, ωi(1)\omega_i^{(1)} and ωi(2)\omega_i^{(2)}. Before each task, the task generator records an index kt∈{1,2}k_t\in\{1,2\} from the stated objective: distinct buyers (1) or orders (2) in LAB DB, and one apple (1) or two apples (2) in ALFWorld. Every memory uses ωi(kt)\omega_i^{(k_t)} in Eq. (7), and each gate record caches ktk_t, so its delayed credit updates only that residual through Eq. (12). The index identifies the task requirement, not whether a memory helps or hurts. No contribution labels enter training, and all other settings are unchanged. We report exposure and success separately for interactions 1–100 and 101–200 as mean ± sample SD over three paired seeds.

DatasetResidual1–100 Exposure A/B1–100 Success A/B101–200 Exposure A/B101–200 Success A/B
LAB DBFixed-zero6.7±0.2/5.5±0.141.1±4.1/33.0±3.16.9±0.2/5.3±0.442.9±4.3/32.2±2.2
LAB DBGlobal13.6±2.5/11.5±2.043.2±4.8/27.3±5.019.2±2.6/18.5±2.145.6±4.9/23.5±5.9
LAB DBConditioned9.2±1.1/5.7±0.442.4±2.3/26.7±3.419.7±1.8/2.6±0.143.0±2.6/34.7±3.6
ALFWorldFixed-zero7.1±0.3/5.9±0.377.2±2.6/52.4±0.77.1±0.2/6.1±0.276.8±2.6/53.2±1.5
ALFWorldGlobal1.6±0.8/2.2±0.276.2±2.9/55.9±3.00.8±0.3/0.8±0.474.6±3.2/58.1±2.7
ALFWorldConditioned7.8±1.0/3.4±0.477.3±1.6/53.6±2.113.3±1.4/1.8±0.679.1±0.6/54.3±1.0

With the same credits, separate residuals split exposure as intended, but slower learning offsets their success gains. By interactions 101–200, the conditioned variant exposes the memory far more in A than in B, with gaps of 17.1 and 11.5 points on LAB DB and ALFWorld. The global residual instead follows the net sign of the memory: it raises exposure in both contexts on LAB DB, hurting B, and suppresses it in both on ALFWorld, hurting A. Conditioning recovers success in exactly these two contexts but loses some in the other two, because each residual receives only about half of the feedback. Over the full run, the two variants therefore stay within 1.8 points of each other on both benchmarks. The limit under rapid sign flips thus lies in what a shared scalar can represent, not in the credits, which are correct in sign in both contexts. Conditioning addresses this limit at the cost of variance, because splitting unbiased but noisy credits (Proposition 3) across contexts slows learning. CMPO therefore pools all feedback into one residual per memory by default. Since the estimator does not depend on the parameterization (Proposition 2), conditioning remains an option for long deployments with a task-type signal.

Reviewer_WSGTOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how a frozen, API-accessed agent should select memories from its growing experience bank. It argues that updating every retrieved memory toward the same trajectory return can reinforce irrelevant or harmful entries. CMPO assigns each memory a semantic score and a learned residual, then samples Bernoulli inclusion gates while respecting a token budget. It uses the observed return, a cached state baseline, and the recorded gate probability to construct signed inclusion/exclusion credit. Delayed updates change the residuals without updating the agent. The analysis establishes unbiasedness for a gate-local return contrast and derives its conditional variance. Experiments cover LifelongAgentBench, ALFWorld, and AppWorld, with controlled memory probes, component ablations, and frozen-memory transfer evaluations.

Critical strengths
  1. A practical method with a well-defined local target. Randomizing memory exposure avoids requiring the frozen agent's gradients or action probabilities. The estimator includes excluded gates, and the treatment of the budget and delayed returns is explicit. The variance formula and normalized update bound make the consequences of small propensities inspectable. Appendix C also correctly limits the result: an executed-gate contrast need not equal the marginal contrast when the budget binds, and local sign alignment does not guarantee global monotonic improvement.

  2. The strongest results are the black-box LAB improvements, with positive paired intervals for both OS metrics and most DB comparisons in Table 5. The controlled experiment tests a plausible failure of shared-return utilities. The authors also evaluate frozen memories on disjoint tasks in Table 7, which addresses an important concern about repeatedly solving the same tasks. Sharing task orders, prompts, the writer, and retrieval budgets makes the comparisons easier to interpret; the paper explicitly identifies Mem0/MemP as modified shared-writer variants.

Critical weaknesses
  1. The experiments do not yet isolate the benefit of this credit update from gradient scaling. In the unclipped region, Eq. 11 equals (G−b)(z−p)p(1−p)\frac{(G-b)(z-p)}{p(1-p)}; the ordinary logit-gradient ablation has expectation p(1−p)Δgatep(1-p)\Delta_{\mathrm{gate}} and already has the correct sign. Thus this comparison changes the update scale and clipping behavior, rather than introducing versus removing valid credit assignment. Table 6 is a valuable control, but it does not report separately tuned learning rates or paired uncertainty for this comparison. Some differences are modest: AppWorld TGC improves by 1.1 points on GPT and 0.4 on Claude. Evidence that the advantage survives a fair learning-rate comparison would make the proposed mechanism more convincing.

  2. The credit-recovery test is narrower than the deployment claim. Table 2 uses three fixed memories, independent gates with probability 0.5, and no token constraint. It therefore tests the particularly simple case in which the local and marginal contrasts coincide. Its very large MAE reductions also compare a contrast estimator with baseline utilities that estimate a different quantity. This is informative about those utilities, but does not establish accurate credit under adaptive, imbalanced exposure and budget competition. The estimator's sample count, averaging procedure, and uncertainty relative to the 20-rollout-per-subset reference need clarification. The downstream evidence helps, although three seeds leave broad intervals for ALFWorld macro success and AppWorld TGC in Table 5. These distinctions matter when interpreting “sustaining accurate credit attribution” during deployment.

Questions for authors
  1. For Table 6's logit-gradient control, was its learning rate tuned independently with the same tuning budget? Please provide the existing seed-wise paired differences against full CMPO and explain how the different update scales and clipping were handled. This would clarify whether the comparison supports an advantage beyond gradient rescaling.

  2. For Table 2, do the credit estimates and the 20-rollout-per-subset oracle use the same return horizon? Please specify the number of observations used for each estimate, the averaging procedure, and how uncertainty in both estimates enters the reported MAE. This would clarify whether the probe measures the same return contrast targeted by the implemented update.

1 comment

Dear Reviewer WSGT,

Thank you again for your careful review. With the discussion period closing soon, we summarize the analyses you requested:

  • Independent tuning with equal budgets (W1, Q1). With five step sizes per method, CMPO keeps the highest mean in all ten backbone–metric pairs, and doubling the control's budget does not change this. Both methods use the same clipping bounds, and we report seed-wise paired differences with intervals.
  • Table 2 details and uncertainty (W2, Q2). We now specify the horizon, sample counts, and averaging. A fivefold larger reference budget changes CMPO's MAE by at most 0.3, and the advantage holds for banks of 32–128 entries with imbalanced propensities.

Do these analyses address your concerns? We are happy to report any further statistics you would find useful.

Best regards, The Authors

Reviewer_YbBNOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper establishes the theoretical analysis of memory credit analysis: co-retrieved memories cannot be distinguished from each other from the signal outcome signal regarding the credit assignment. To address the memory credit leakage issue in the common agent's long-term memories, the authors proposed a novel framework, Credit-Aware Memory Policy Optimization (CMPO), with two components: policy-guided memory selection and propensity-corrected credit optimization. The authors show the expected credit assignment unbiased estimator of the gate-local return contrast between inclusion and exclusion of the memories conditional on the pre-gate history. The benchmarks using various backbone LLMs demonstrate the effectiveness of the proposed CMPO in removing the memory credit leakage issue.

Critical strengths
  • This paper formulates the memory credit leakage with inflated returns, where the agent is exposed to irrelevant or harmful memory items, and establishes a very thorough analysis of the memory credit leakage by modeling the contrast between the inclusion and exclusion-conditioned returns.
  • The proposed CMPO framework is designed to translate the joint returns into distinct updates for included and excluded memories, directly addressing the challenges in memory credit leakage. The authors conducted thorough empirical analysis on the proposed CMPO framework, validating its effectiveness in credit recovery and leakage prevention.
Critical weaknesses

To be honest, I wanted to mention that I don't fully understand the theoretical analysis of the proposed method in Section 3; thus, my reviews of critical weaknesses are mostly based on the experimental results.

  • Across benchmarks with various backbone LLMs, the proposed CMPO didn't achieve consistent improvements, and the authors failed to analyze why CMPO underperforms the baselines under those settings. The authors also didn't compare latency or efficiency with other baselines.
  • In Table 2, the credit recovery is computed on a small subset of examples, with only 3 memory items. It is unclear if the results still hold with a larger number of samples and a reasonable memory bank size.
Questions for authors
  • Based on my understanding, each memory item from the memory bank is modeled independently to compute the inclusion and exclusion conditioned returns. Could the authors clarify what happens if the memory items in the memory bank are related to each other, and how the CMPO algorithm handles the co-occurrence of multiple memory items?
2 comments

Dear Reviewer YbBN,

Thank you again for your review. With the discussion period closing soon, we summarize our response to your concerns:

  • Section 3 (W1, Q1). CMPO does not assume that memories are independent. Each credit is computed from the joint return, so it measures what a memory adds given the memories it co-occurs with. We will add this intuition to Section 3.
  • Efficiency (W3). CMPO's latency stays within 3.3% of the fastest baseline in every setting.
  • Larger memory banks (W4). With banks of 32–128 entries, CMPO's credit error stays at least 69% below the strongest baseline.

Do these clarifications resolve your questions, especially on Section 3? We are happy to explain any part in more detail.

Best regards, The Authors

Reviewer_YbBNOpenReview ↗

Response to authors

Thank you for your clarifications and sorry for the late reply. My major concerns have been addressed, and I'm raising my rating to 4.

Reviewer_pHVPOpenReview ↗
Rating
1
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper is to randomly gate each candidate memory, weight the task reward using its recorded inclusion probability, estimate the credit of each memory from a single execution, and then update its retrieval probability.

Critical strengths

When multiple memories are included in the context, using the same task reward to update all of them may reinforce irrelevant or even harmful memories. CMPO addresses this issue by optimizing memory selection without requiring access to model parameters, gradients, or output probabilities, and without running additional counterfactual trajectories for each memory, making it practical for real-world applications. The appendix further analyzes the variance, baseline, and update magnitude, while clearly distinguishing local directional consistency from global optimization guarantees. These analyses provide reasonable theoretical support for the algorithm.

Critical weaknesses

Equation (11) is essentially a score-function estimator for Bernoulli gating. In the unclipped region, it is equivalent to rescaling the standard logit policy gradient by the product of the inclusion and exclusion probabilities. Therefore, the paper should more clearly distinguish existing inverse-probability estimation from its novel memory optimization mechanism. Table 2 uses the reward difference between inclusion and exclusion as the ground truth. However, the original scores of MemRL and MemQ are mainly designed to estimate rewards or retrieval utility rather than this difference. Comparing their MAE against this ground truth shows that they optimize different objectives, but does not establish that CMPO is superior to other reasonable contribution estimators. The authors report confidence intervals, but several of them cross zero. Moreover, in Table 6, removing inverse-probability correction still achieves performance close to the full method. Since this variant uses the standard logit gradient with a different signal scale, its learning rate should be tuned independently to determine whether the gain comes from the correction mechanism or simply from the update scale. Directly deleting memories with low estimated utility may introduce a risk of overfitting to the limited interactions used for credit estimation, potentially removing information that could become useful in future tasks.

Questions for authors

After effective memory consolidation, deduplication, and integration, does the credit leakage problem emphasized in this paper remain significant? How much additional improvement can CMPO provide over such strong baselines? In fact, I believe that the paper compares against relatively outdated baselines. With commonly used memory consolidation techniques, most information is already summarized and integrated, which largely avoids retaining excessive harmful or irrelevant information. Could the authors include comparisons with Memory-R2 and HiMPO, and report results under both the same interaction budget and the same total inference cost? After independently tuning the learning rate, does the standard logit policy gradient still perform significantly worse than CMPO? As the memory bank continues to grow, how many interactions are required to reliably evaluate a newly added memory?

1 comment

Dear Reviewer pHVP,

Thank you again for your detailed review. With the discussion period closing soon, we summarize our response to your main concerns:

  • Relation to inverse-probability estimation (W1, W4, Q3). Our contribution is the mechanism that makes this identity usable for black-box agents. After independent tuning with twice CMPO's budget, the logit-gradient control does not exceed CMPO's mean in any of ten backbone–metric pairs.
  • Recent baselines and consolidation (Q1, Q2). CMPO exceeds Memory-R2 at matched interactions and matched cost. On native Mem0's consolidated bank, it improves all five metrics by 2.4–17.5 points.
  • Memory deletion (W5). CMPO never deletes memories based on credit. It only lowers their exposure.

Do these results address your concerns? We are happy to clarify any remaining point.

Best regards, The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.