Identify Then Reinforce: Action-Level Credit for Graph-Structured Memory Agents

Personal memories are interdependent: new experiences can update earlier facts, introduce conflicting claims, or connect to related information from distant interactions. Existing learnable memory systems primarily operate on flat textual entries, leaving these relationships implicit and making it difficult to reconcile evolving information and retrieve related evidence across time. We introduce PersonaMap, a relational memory framework that learns how personal memories should be extracted, organized, and accessed. To learn memory construction and retrieval jointly, we propose a shared policy strategy that extracts atomic claims from interaction histories, constructs semantic relations, and navigates the Personal Memory Graph through tool interactions. To distinguish the contributions of individual memory actions, we infer action-level credit from outcome differences across natural rollouts and invoke counterfactual rollouts only when natural evidence is insufficient to identify an action's effect. PersonaMap further supports structure-aware forgetting that prunes weakly connected claims while preserving strongly connected memories within the graph. Across two personalized long-term memory benchmarks, PersonaMap improves overall accuracy over the strongest baselines by 7.68% and 4.29% respectively. Controlled comparisons support the benefit of action-level credit. With 50% fewer stored claims, structure-aware forgetting retains complete mapped relational evidence for approximately 80% of eligible questions.