MemQ: Integrating Q-Learning into Self-Evolving Memory Agents over Provenance DAGs

Computer Science > Artificial Intelligence [Submitted on 8 May 2026] MemQ: Integrating Q-Learning into Self-Evolving Memory Agents over Provenance DAGs Junwei Liao, Haoting Shi, Ruiwen Zhou, Jiaqian Wang, Shengtao Zhang, Wei Zhang, Weinan Zhang, Ying Wen, Zhiyu Li, Feiyu Xiong, Bo Tang, Muning Wen Episodic memory allows LLM agents to accumulate and retrieve experience, but current methods treat each memory independently, i.e., evaluating retrieval quality in isolation without accounting for the dependency chains through which memories enable the creation of future memories. We introduce MemQ, which applies TD(\lambda) eligibility traces to memory Q-values, propagating credit backward through a provenance DAG that records which memories were retrieved when each new memory was created. Credit weight decays as (\gamma\lambda)^d with DAG depth d, replacing temporal distance with structural proximity. We formalize the setting as an Exogenous-Context MDP, whose factored transition decouples the exogenous task stream from the endogenous memory store. Across six benchmarks, spanning OS interaction, function calling, code generation, multimodal reasoning, embodied reasoning, and expert-level QA, MemQ achieves the highest success rate on all six in generalization evaluation and runtime learning, with gains largest on multi-step tasks that produce deep and relevant provenance chains (up to +5.7~pp) and smallest on single-step classification (+0.77~pp) where single-step updates already suffice. We further study how \gamma and \lambda interact with the EC-MDP structure, providing principled guidance for parameter selection and future research. Code will be available soon. Comments: 22 pages, 11 figures (containing 43 individual image panels total) Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2605.08374 [cs.AI]   (or arXiv:2605.08374v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2605.08374 Focus to learn more Submission history From: Junwei Liao [view email] [v1] Fri, 8 May 2026 18:30:24 UTC (9,355 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-05 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)