arXiv CSopen access

Memory as a Controlled Process: Learned Adaptive Memory Management for LLM Agents

Memory as a Controlled Process: Learned Adaptive Memory Management for LLM Agents

Eric Hanchen Jiang1* , Zhi Zhang1* , Yuchen Wu2 , Levina Li1 , Dong Liu1 , Xiao Liang1 , Rui Sun1 , Yubei Li1 , Edward Sun1 , Haozheng Luo3 , Zhaolu Kang , Aylin Caliskan2 , Kai-Wei Chang1 , Ying Nian Wu1† 1

University of California Los Angeles, 2 University of Washington, 3 Northwestern University

arXiv:2607.13591v1 [cs.CL] 15 Jul 2026

Abstract Large Language Model (LLM) agents increasingly rely on external memory systems to accumulate experience across tasks. Yet nearly all existing approaches, from graph-structured memories to reflective insight stores, access memory through fixed, hand-designed heuristics. We argue that this static view of memory is a core bottleneck for agentic learning because optimal memory behavior is fundamentally context-dependent. The early stages of the tasks, benefit from minimal retrieval because memory is sparse; recurring goal types benefit from plan reuse rather than generic nearest-neighbor lookup; stuck agents benefit from re-retrieval with alternative queries; and across long task streams, the memory store itself must be consolidated and pruned to remain useful. We present M EM C ON (Memory as a Controlled Process), a framework that models memory operations as a Markov Decision Process and learns an online policy that adaptively decides when, what, and how much to retrieve, when to inject a distilled plan, and when to consolidate or forget. M EM C ON is backend-agnostic: it wraps any existing memory implementation, learns from task-by-task binary feedback with no pretraining and no additional LLM calls, and uses a lightweight tabular contextual bandit with UCB exploration that converges within tens of tasks. Across 6 benchmarks, 3 agent frameworks, and 3 LLM backbones, M EM C ON consistently outperforms multiple memory baselines by up to 15.2 points in task success while reducing token consumption by 5–20%. Our code is available at https://github.com/ericjiang18/MemCon/

1

Introduction

Large Language Models (LLMs) deployed as autonomous agents have demonstrated remarkable capabilities in interactive environments, multi-step planning, and tool use [1–4]. A critical enabler of this progress is memory, the ability to store experiences from solved tasks and retrieve them on future ones, so that an agent can avoid repeating past mistakes, reuse working strategies, and incrementally accumulate domain knowledge rather than starting from scratch on every episode [5–9]. Despite rapid progress in what to store (trajectories, reflections, insights, skills, graphs, latent tokens [5, 9–13]), most existing memory systems treat memory access as a static pipeline: a single global retriever is called once per step with a hard-coded top-k, a hard-coded graph hop depth, and a hard-coded query template, and uses the same configuration whether memory is empty or contains thousands of trajectories, whether the task is familiar or novel, and whether the agent is * Equal contribution. † Corresponding author: Ying Nian Wu ([email protected]).

Preprint.

progressing or has been executing the same action for five steps. A complementary line of work— most prominently MemGPT [11]—makes memory access adaptive by promoting the LLM itself to the role of memory controller (paginating, formulating queries, and deciding when to recall), at the cost of an additional LLM call per memory operation. M EM C ON occupies a third design point: a learned but lightweight controller that is adaptive without any extra LLM calls. We show this static-pipeline view is a fundamental bottleneck for agentic memory systems: existing static memory systems either retrieve too aggressively (inflating context and cost while hurting accuracy on simple queries) or too conservatively (missing key reusable plans and reflections), because any single setting is miscalibrated for at least one of the regimes above. We argue that effective agent memory requires an adaptive control layer sitting on top of the storage backend. Concretely: (i) Early tasks should retrieve less, because there is little useful experience to draw on and indiscriminate retrieval only dilutes the prompt. (ii) Recurring goal types should prefer plan reuse, replaying a distilled, object-generalized template of a prior success, rather than nearest-neighbor retrieval over raw trajectories. (iii) Stuck agents that repeat actions should trigger re-retrieval with an alternative query rather than re-reading the same top-k that already failed to help. (iv) Long task streams require consolidation and forgetting so that a growing, noisy memory remains useful rather than overwhelming. No single fixed heuristic achieves all four; the right memory operation is a function of task progress, memory state, and the agent’s learning phase. We introduce M EM C ON (Memory as a Controlled Process), a framework that reformulates memory access as a sequential decision problem. M EM C ON casts the choice of memory operation (R ETRIEVE, P LAN I NJECT, R E -R ETRIEVE, C ONSOLIDATE, F ORGET, N O O P) together with its parameters (top k, insight k, graph hop) as actions in a Memory MDP, whose state captures both task progress (goal type, step phase, stuck indicator, locations visited) and memory status (size, plan availability, learning phase). M EM C ON learns a policy over this MDP online, during deployment, using a lightweight tabular contextual bandit with UCB exploration [14–16]. The policy is warm-started from humanreadable priors, updated via reverse-discounted credit assignment from binary task success, and persists to disk between tasks. Crucially, M EM C ON adds zero additional LLM calls: memory control is a millisecond-scale table lookup, not a second LLM invocation. M EM C ON is not a new memory store. It is a thin wrapper that intercepts the abstract retrieve and store entry points of any existing memory backend and decides how to call them. The same wrapper applies unchanged to flat vector stores, skill libraries [8], summarisation-based memories [17], latenttoken memories [10], and graph-structured memories [9], cleanly separating what is stored (backend) from how it is accessed (controller) and letting any future memory system plug in and inherit adaptive control. We evaluate M EM C ON across 6 benchmarks covering both interactive decision-making (ALFWorld [18], PDDL planning, ScienceWorld [19]) and knowledge / web / tool-use QA (TriviaQA [20], WebWalkerQA [21], GAIA [22]); 3 agent frameworks (Lobster, LangGraph [23], Microsoft AgentFramework); 3 LLM backbones (GPT-4.1-mini, Claude Sonnet-4, DeepSeek-V3.2); and compare against 9 strong memory baselines spanning vector retrieval (MetaGPT [24], MemoryBank [17]), skill libraries (Voyager [8]), trajectory summarization (ChatDev [25]), generative re-ranking (Generative [5], ExperienceBank), insight-based learning (OAgents [26]), graph-based hierarchical memory (G-Memory [9]), and latent-token memory (LatentMem [10]). Across all configurations, M EM C ON achieves the best or near-best task success—e.g., 67.9% ALFWorld on GPT-4.1-mini (Lobster), the top score among all 10 memories evaluated in that cell—and consistently delivers 5–30+ point gains over the no-memory baseline, while simultaneously reducing average token consumption per task by 5–20%. Contributions.

1. We formalize agent memory management as a Memory MDP and introduce a backend-agnostic wrapper that decouples the memory control policy from the memory storage backend, so any existing or future memory system inherits adaptive control for free (§3.1, §3.3). 2. We propose an online contextual bandit policy with UCB exploration, warm-start priors, and reverse-discounted credit assignment that converges within tens of tasks using zero pretraining and zero extra LLM calls, together with augmented memory operations (§3.2, §3.3). 2

3. We conduct an extensive evaluation of agent memory on six benchmarks and three agent frameworks, showing consistent accuracy gains and token savings, including a component ablation that isolates the learned controller’s contribution (§4).

2

Related Work

M EM C ON builds on three lines of work: (i) multi-agent reinforcement learning, (ii) multi-agent LLM systems, and (iii) agentic memory. Reinforcement Learning for Memory and Tools. Reinforcement learning has long been used to learn task policies from sparse reward, including value-decomposition (VDN [27], QMIX [28]), centralized-critic actor-critic (MADDPG [29], COMA [30]), and on-policy methods (MAPPO [31], IPPO [32]) on cooperative benchmarks such as SMAC [33]; learning to communicate [34] and sequence-modelling views [35], with surveys [36–39], broaden the design space. Closer to our setting, several recent works learn memory-management policies for LLM agents using deep RL or LLM-driven controllers [11]; we operate in a much lighter-weight regime, treating memory operations as actions of a single-agent contextual bandit [14, 15, 40] (a special case of tabular Qlearning [16, 41]) with episode-level Monte-Carlo updates. The resulting MDP is small enough to be learnable online without GPUs and without secondary LLM calls. Multi-Agent LLM Systems. Role-based LLM collaboration (AutoGen [42], CAMEL [43], MetaGPT [24], ChatDev [25], AgentVerse [44]), multi-agent debate [45, 46], and society-of-minds formulations [47, 48] improve reasoning over single-agent baselines, while more recent work optimizes the collaboration graph itself [49, 50]; production frameworks such as LangGraph [23] and Microsoft Agent-Framework supply the execution substrates we evaluate; see [51, 52] for surveys. These systems delegate cross-task learning to an external memory with fixed retrieval parameters. M EM C ON sits inside that memory module, so it is compatible with single-agent (Lobster), graph (LangGraph), and pipeline (Agent-FW) orchestration unchanged. Agentic Memory. Retrieval over stored experience is the dominant paradigm. Memory streams, long-term stores, and OS-style paging: Generative Agents [5], MemoryBank [17], MemGPT [11], Mem0 [12], MemLLM [53], Think-in-Memory [54], and memory-assisted prompt editing [55]. Skill- and procedure-centric memories: Voyager [8], MemP [13], Agent Workflow Memory [56], ProcMEM [57], MemSkill [58], HiAgent [59], and LatentMem [10]. Reflection- and rule-based memories: Reflexion [6], ExpeL [7], CLIN [60], OAgents [26], and the graph-structured G-Memory [9], our strongest baseline. These build on RAG [61–63]. Most of these systems access memory with fixed top-k, hop, query, and consolidation schedule; the notable exception is MemGPT [11], which makes the access pattern adaptive by promoting the LLM itself to the role of controller, at the cost of additional LLM calls per memory operation. M EM C ON is orthogonal to both styles: it adds a learned-but-lightweight controller on top of any backend—deciding which operation, with what parameters, and when—without any secondary LLM calls.

3

Method

This section formalizes each component: the Memory MDP (§3.1), the online policy (§3.2), the backend-agnostic wrapper (§3.3), and two augmented memory operations tailored to long-horizon agentic tasks (§3.3). Figure 1 gives a high-level overview of M EM C ON. 3.1

Problem Formulation: Memory MDP

Consider an LLM agent solving tasks {τ1 , . . . , τN } sequentially. At each task τi , the agent interacts with an environment over Ti steps with access to a memory system M (the backend). Most existing memory backends expose two abstract endpoints, a retrieve call (return up to K items relevant to a query) and a store call (write the trajectory of the just-finished task), together with optional maintenance hooks for consolidation and eviction. In standard usage these endpoints are invoked with hard-coded hyperparameters (number of items, search depth, query template, consolidation schedule); we instead model the choice of which endpoint to invoke and with what parameters as a sequential decision problem captured by an MDP Mmem = (S, A, T , R, γ). 3

Memory Markov Decision Process

Online Policy Learning

Step 1: State Extraction

Task Query 𝓠 Topic: Common Household Tasks

Task State Step Phase

Challenge: Multi-step “pick and place” task

Examine a bar of soup in the light of a floor lamp. Topic: Strategic Planning

Move three crates from Warehouse A to Warehouse B using a single truck with limited fuel. Topic: Science Simulations Challenge: Require understanding state changes and using specific tools in sequence

Boil a breaker of water using a Bunsen Burner and record the temperature change.

Goal Location Type Visited

Discretization

Challenge: Logic puzzle involving resource constraints

1. Action Selection

Memory State

Is Stuck

𝑎" = arg max 𝒬 𝜙 𝑠" , 𝑎 + 𝑐 Exploration

𝝓

2.Update Rule

𝝓 UCB Policy

Policy Q-Table

Intercepting Specific k hop

Re- Forget NoOp Retrieve Retrieve

Exploitation

Memory Backend (Vector Store)

𝒬 𝜙! , 𝑎! ← 𝒬 𝜙! , 𝑎! + 𝛼[𝛾 "# $!$% * 𝑟& − 𝒬(𝜙! , 𝑎! )]

Answers to The Three Queries

LLM Output

Topic: Common Household Tasks

Topic: Strategic Panning

LLM Reasoning: Go to bathroom, pick up soap, go to living room, use lamp.

LLM Reasoning: The LLM LLM Reasoning: calculates the fuel-to-weight "Temperature reached 100°C ratio and realizes it must move and plateaued." It concludes two crates first, then the third. the water is boiling.

Answer: The agent successfully moves to the lamp and executes the examine command. The episode ends with Success (+1.0), reinforcing that a "Shallow Retrieval" is sufficient for object localization.

REWARD +1.0 (Success + Bonus) -0.5 (Failure)

Model & Hyperparameters

Reverse-Discounted Reward

Results/Plans

Step 5: Episode Logging & Reward Lobster LangGraph Agent-FW

State-Action

State-Action History

Step 4: Reasoning & Response Generation

Agent Frameworks

Claude

𝑁# 𝜙 𝑠"

Consolidate

…

Selected Action

Step 3: Backend-Agnostic Wrapper

Retrieved Memory

DeepSeek

Plan Inject

ln 𝑁

Step 2: Decision Making

Injecting

ChatGPT

Action Space

Improver-making

Learning Memory Phase Size Plan Available

Task Completion

Note:

Big Step

Answer: A multi-step logistical plan that respects the fuel constraint. The Success (+1.0) reward is back-propagated to the PLAN_INJECT action for this "stuck" state.

Detailed Step

Explanation

Topic: Science Simulations

Answer: The agent records the state change at 100°C. The reward includes an Efficiency Bonus because by consolidating memory, the LLM used fewer tokens and steps to reach the conclusion.

Figure 1: Overview of M EM C ON. (Left) Task streams from ALFWorld, PDDL, and ScienceWorld are executed through three agent frameworks (Lobster, LangGraph, Agent-FW) sharing one LLM backbone. (Middle) The Memory MDP runs four steps per retrieval: extract a compact state ϕ(s) from task + memory signals; select an action via the UCB policy over Q(ϕ, a); the backend-agnostic wrapper issues retrieval to the inner backend with policy-chosen top k/insight k/hop; retrieved context (optionally plus an injected success plan) is fed to the LLM, and the episode is scored (+1 success, −0.5 failure, plus efficiency bonus). (Right) Online learning: the action space is {R ETRIEVE (varying depth), P LAN I NJECT, R E -R ETRIEVE, C ONSOLIDATE, F ORGET, N O O P}; after each episode the reverse-discounted reward γ |ep|−j−1 ri updates every visited (ϕj , aj ).

State S.

The state s = (stask , smem ) fuses task-progress and memory-status signals: stask = (goal type, step phase, is stuck, objects held, locations), smem = (mem size, plan available, learning phase),

(1) (2)

where step phase bins the step count, is stuck ∈ {True, False} is set when the agent has emitted the same physical action twice in a row, learning phase indicates whether the agent has completed enough tasks to trust learned Q-values, and plan available records whether a distilled success plan exists for the current goal type. We discretize s into a compact hashable key ϕ(s) for tabular learning; the exact bins, thresholds, and the discretization rule are given in Appendix C. The discretization yields on the order of a few hundred distinct states per benchmark, enabling rapid online convergence. Actions A.

Each action a = (op, θ) specifies a memory operation together with its parameters:

op ∈ {R ETRIEVE, P LAN I NJECT, R E -R ETRIEVE, C ONSOLIDATE, F ORGET, N O O P};

(3)

θ = (top k, insight k, hop).

(4)

R ETRIEVE returns the top-top k items from the backend together with up to insight k derived rules (when supported) at search depth hop; R E -R ETRIEVE re-issues a retrieval with an alternativeapproach query suffix, used to escape repeated-action loops; P LAN I NJECT prepends a generalised success plan when one is available (§3.3); C ONSOLIDATE and F ORGET call any maintenance hooks the backend exposes (e.g., merging or pruning derived rules) and silently no-op on backends that do not implement them; N O O P skips memory access for the current step. We instantiate A as a small finite set of representative (op, θ) configurations spanning shallow-to-deep retrieval plus the maintenance and plan operations; the exact action set used in our experiments is listed in Appendix C (Table 7). Reward R.

Rewards are observed at task end based on environment feedback:

r(τi ) = rsucc · ⊮[success] + λ · max(0, 1 − Ti /Tmax ) − rfail · ⊮[failure], 4

(5)

where rsucc , rfail , λ and the horizon Tmax are fixed scalars (values in Appendix C, Table 6). Successful and more efficient trajectories therefore earn larger credit; failed trajectories earn negative feedback that discourages costly or counterproductive memory usage. Transitions T . The environment transition is driven by the LLM agent and is effectively opaque to the controller. We therefore treat Mmem as a contextual bandit with episode-level (Monte-Carlo) feedback: even though the underlying problem is sequential, the controller never bootstraps a withinepisode value estimate and instead receives one terminal-reward signal per task, which makes the formal regret analysis (Appendix D) straightforward and bounds sample complexity to tens of tasks. 3.2

Online Policy Learning

We learn π : S → A online during deployment, with no pretraining and no additional LLM calls. Action selection via UCB. At each memory decision point we apply the Upper Confidence Bound rule [14, 15], with the exploration bonus computed using the state-specific visit count: s " # ln N (ϕ(st )) at = arg max Q(ϕ(st ), a) + c , (6) a∈A Na (ϕ(st )) P where c is the UCB exploration coefficient (Appendix C, Table 6), N (ϕ(st )) := a∈A Na (ϕ(st )) is the total number of decisions ever taken at state key ϕ(st ), and Na (ϕ(st )) is the count of action a at that state. Unvisited actions receive an ∞ bonus, forcing the first |A| visits to each state to span all actions; warm-start priors (below) break ties among such ∞ bonuses to give a sensible initial ordering. The same expression is used both in the implementation (with the per-state count) and in the theoretical analysis (Appendix D, Eq. (16)). Warm-start priors. Before any learning, Q-values are initialized with interpretable priors that encode mild domain knowledge: R ETRIEVE and P LAN I NJECT receive positive priors (retrieval is usually helpful, plans are useful when available), R E -R ETRIEVE a smaller positive prior (useful only when stuck), C ONSOLIDATE a neutral prior, and F ORGET and N O O P mildly negative priors. Numerical values are listed in Appendix C (Table 6). Warm-starting accelerates convergence on the first few tasks, before any real reward has been observed. Credit assignment. After each task τi , all (s, a) pairs visited during the episode are updated with a reverse-discounted Monte-Carlo return, so that actions taken closer to the terminal outcome receive stronger credit: h i Q(ϕj , aj ) ← Q(ϕj , aj ) + α γ |ep|−j−1 · ri − Q(ϕj , aj ) , (7) where α is the step size, γ ∈ (0, 1) is the within-episode discount, |ep| is the total number of memory decisions executed during episode τi , and j ∈ {0, 1, . . . , |ep| − 1} is the chronological index of the decision being credited (so the last decision receives the undiscounted ri and earlier decisions receive geometrically attenuated credit). Numerical values for α and γ are in Appendix C. The Q-table is persisted to disk every few updates, so learning carries across runs and task streams. 3.3

Backend-Agnostic Wrapper and Augmented Operations

M EM C ON is a thin wrapper around any memory backend Minner that exposes a two-method interface: retrieve (return K items for a query) and store (write the finished trajectory with its success label); an optional maintain hook unlocks the consolidation and eviction actions, and is silently no-op’d otherwise. On retrieve, the wrapper builds st , invokes the policy to pick (op∗ , θ∗ ), calls Minner with those parameters (unsupported parameters are dropped), and optionally augments the result with one of two domain-agnostic augmented operations (described below); on store, it computes the episode reward, updates Q-values via Eq. (25), updates the plan index, and delegates persistence to Minner . Because the wrapper never reads or mutates the backend’s internal data structures, it is genuinely backend-agnostic and applies unchanged to flat vector stores [17, 24], skill libraries [8], summarisation-based memories [25], latent-token memories [10], and graph-structured memories [9]. The two augmented operations target failure modes in long-horizon interactive tasks: generalised 5

plan injection (a learnable MDP action, P LAN I NJECT) extracts the action sequence of a successful task of type g, replaces instance-specific identifiers (e.g. ‘‘shelf 3’’ → [shelf]) via a regex rewriter, stores the resulting template under g in a lightweight JSON index, and on future tasks of type g prepends the template to the backend’s retrieval output (the rewriter degrades to identity on new vocabularies); goal decomposition (a deterministic heuristic, not an MDP action) handles composite tasks requiring the same primitive twice with two objects (e.g., “put two cellphones on the desk”) by injecting “complete all steps for object 1 first, then repeat for object 2” and additionally retrieving the single-object template when one exists. Both augmentations consume only the action transcript and concatenate text to the retrieved context, so they are independent of the backend; the component ablation (§4.3, Table 4) shows that the learned controller alone already accounts for the majority of M EM C ON’s gains, making both augmentations useful but optional. Interactive (S/A %) Framework Memory

QA (S/A %)

Avg.

ALFWorld PDDL SciWorld TriviaQA WebWalkerQA GAIA

Lobster

Empty G-Memory MetaGPT Voyager Generative ChatDev MemoryBank OAgent ExpBank M EM C ON

43.3 59.7 55.2 53.0 54.5 32.8 57.5 48.5 59.0 67.9

33.3 31.7 33.3 31.7 31.7 28.3 33.3 28.3 33.3 35.0

28.0 34.0 33.0 31.0 36.0 24.0 28.0 34.0 30.0 38.0

69.5 66.5 71.5 71.5 69.5 69.5 69.5 70.5 69.0 71.5

17.9 19.0 18.2 18.4 18.7 17.7 16.3 17.4 17.8 20.6

20.6 21.2 16.4 16.4 18.2 18.2 17.6 19.4 20.0 22.4

35.4 38.7 37.9 37.0 38.1 31.7 37.0 36.4 38.2 42.6

LangGraph

Empty G-Memory MetaGPT Voyager Generative ChatDev MemoryBank OAgent ExpBank M EM C ON

31.3 68.7 57.5 59.7 56.0 39.6 57.5 53.7 55.2 68.7

30.0 28.3 38.3 33.3 35.0 33.3 31.7 30.0 35.0 40.0

39.0 38.0 35.0 40.0 36.0 27.0 29.0 37.0 41.0 40.0

67.5 69.0 69.0 67.5 66.0 67.5 70.0 68.0 68.0 69.0

18.6 20.9 18.3 17.5 18.0 18.1 18.7 18.1 18.2 20.2

19.4 20.0 18.2 20.0 20.0 18.8 18.8 18.8 20.0 22.4

34.3 40.8 39.4 39.7 38.5 34.1 37.6 37.6 39.6 43.4

Agent-FW

Empty G-Memory MetaGPT Voyager Generative ChatDev MemoryBank OAgent ExpBank M EM C ON

38.1 70.2 55.2 54.5 50.0 32.1 59.0 63.4 52.2 71.0

33.3 33.3 30.0 36.7 35.0 31.7 33.3 30.0 36.7 40.0

26.0 28.0 38.0 36.0 37.0 31.0 30.0 37.0 35.0 38.0

69.0 66.0 68.5 67.5 68.0 66.5 69.5 69.0 66.5 69.0

18.1 19.4 17.9 17.1 18.3 17.8 18.7 18.1 17.5 20.9

16.4 20.0 18.8 19.4 18.8 19.4 16.4 18.2 17.0 23.0

33.5 39.5 38.1 38.5 37.8 33.1 37.8 39.3 37.5 43.6

Table 1: Main results with GPT-4.1-mini backbone. S/A = task success rate / answer accuracy (%) on three interactive benchmarks (ALFWorld, PDDL, ScienceWorld) and three QA/tool-use benchmarks (TriviaQA, WebWalkerQA, GAIA), against 9 memory baselines, evaluated under three agent frameworks (Lobster, LangGraph, Microsoft Agent-FW). Avg. is the arithmetic mean across the six benchmarks. Bold: highest S/A per column within each framework block (ties bolded). Underline: second-best S/A per column within each framework block. Token-cost numbers and per-backbone results for Sonnet-4 and DeepSeek-V3.2 are reported in Appendix B.

4

Experiments

We design our evaluation to answer four questions: (Q1) Does learned memory control improve over the best fixed-pipeline memory systems, across backends, benchmarks, frameworks, and LLM backbones? (Q2) Does M EM C ON deliver these gains while using fewer tokens per task, or do the improvements come from simply retrieving more? (Q3) Does M EM C ON generalize beyond interactive decision-making to QA and web/tool-use settings? (Q4) Is M EM C ON robust under different LLM backbones, including weaker (GPT-4.1-mini), strong proprietary (Sonnet-4), and open-source (DeepSeek-V3.2) models. 6

Query

Case 1: WebWalkerQA

Case 2: GAIA Query Calculate the total energy consumption of a 60W bulb running for 8 hours a day over a leap year, and suggest an energyefficient alternative

Compare the stock prices of [company A] and [company B] on the day the Federal Reserve last raised interest rates.

Step 1: State Observation

Step 1: State Observation

Task State(stask): (goal: compare_stocks, phase: early, objects: none, locations: start, subgoals: 0/1).

Task State(stask): (goal: calculation_recommendation, phase: early, objects: bulb, locations: none, subgoals: 0/2).

Memory State(smem): (mem_size: 0, plan_available: False, learning_phase: cold).

Memory State(smem): (mem_size: 12, plan_available: True, learning_phase: warm).

Step 2: Action Selection via UCB (A) ≈

Step 2: Action Selection via UCB (A)

Formula: 𝑎" = arg max 𝒬 𝜙 𝑠" , 𝑎 + 𝑐 ln 𝑁 /𝑁! 𝜙 𝑠"

Formula: 𝑎" = arg max 𝒬 𝜙 𝑠" , 𝑎 + 𝑐 ln 𝑁 /𝑁! 𝜙 𝑠"

Since the agent is in the cold phase, 𝑁! 𝜙 𝑠" = 0, causing the bonus term to be ∞. This forces exploration and leads the controller to select a1 = RETRIEVE with parameter 𝜃 = (top k = 1, hop = 0).

The policy selects a1 = PLANINJECT with 𝜃 = top k=2, hop=1 because Q(PLANINJECT) is high for composite reasoning tasks.

Step 3: Execution & Failure Detection (T)

Step 3: Execution & Failure Detection (T)

Interaction: The agent attempts to search for the specific stock prices directly but fails because the date of the Fed rate hike is unknown, setting <is_stuck = True>.

Plan Injection: The system prepends a generalized template: "Step 1: Identify all numerical constants. Step 2: Apply unit conversion. Step 3: Provide comparative alternatives." Outcome: The LLM agent uses the "leap year" constant (366 days) correctly on the first try: 60W * 8h * 366 days = 175.68kWh.

Transition: The environment transitions to a new state s2 where <phase : mid>.

Step 4: Policy Adaption: RE-RETRIEVE

Step 4: Reward Calculation(R)

Decision: Observing the failure, the policy selects a2 = RE-RETRIEVE.

Formula: r(τi) = rsucc · ⊮[success] + λ · max(0, 1 − Ti/Tmax) − rfail · ⊮[failure]

Augmentation: Find the date of the last Fed hike first.

Parameters: rsucc = 1.0, 𝜆 = 0.3, Tmax = 30, agent finishing in Ti = 5 steps

Step 5: Reward Calculation (R)

Performance: The agent finishes in Ti = 30 steps

Formula: r(τi) = rsucc · ⊮[success] + λ · max(0, 1 − Ti/Tmax) − rfail · ⊮[failure]

Calculation: r(𝜏i) = 1.0 + 0.3 * max(0, 1 – 3/30) = 1.27

Parameters: rsucc = 1.0, 𝜆 = 0.3, Tmax = 30, agent finishing in Ti = 5 steps

Step 5: Q-Update

Calculation: r(𝜏i) = 1.0 + 0.3 * max(0, 1 – 5/30) = 1.25

Formula: 𝒬 𝜙# , 𝑎# ← 𝒬 𝜙# , 𝑎# + 𝛼[𝛾 $% &#&' ; 𝑟( − 𝒬(𝜙# , 𝑎# )]

Step 6: Q-Update

The high reward reinforces the "Plan Injection" strategy for future math/reasoning queries:

Formula: 𝒬 𝜙# , 𝑎# ← 𝒬 𝜙# , 𝑎# + 𝛼[𝛾 $% &#&' ; 𝑟( − 𝒬(𝜙# , 𝑎# )] The RE-RETRIEVE action(a2) receives a higher credit weight (𝛾0) than the initial RETRIEVE (a1), to ensure the system learns to prioritize recovery actions in stuck states.

Update: Q(𝜙', PLANINJECT) ← Q(𝜙', PLANINJECT) + 0.15 [ 0.9^0 * 1.27 - Q(𝜙', PLANINJECT) ]

Figure 2: Step-by-step case study on two qualitatively different queries. Left (Case 1, WebWalkerQA): a multi-hop financial query that requires the agent to navigate the web and identify a specific date. In Step 2 the controller is in the cold learning phase (Na (ϕ) = 0), so the UCB bonus is +∞ and the policy explores with a shallow R ETRIEVE action. After Step 3 reports is stuck=True, the controller switches to R E -R ETRIEVE (Step 4) with the augmented query suffix, which then succeeds; the failure-then-recovery sequence updates Q-values via Eq. 25 so that R E -R ETRIEVE receives more credit in stuck states for future episodes. Right (Case 2, GAIA): a numeric reasoning query for which a generalized success plan already exists (plan available=True, learning phase=warm). The policy directly selects P LAN I NJECT; the prepended template guides the LLM to use the leap-year constant on the first try, and the resulting high reward reinforces the P LAN I NJECT entry for future composite-reasoning queries. Each step shows the exact MDP state, the policy decision (with rule and parameters), the environment outcome, and the resulting Q-update.

4.1

Setup

We evaluate on six benchmarks across two regimes, interactive decision-making (ALFWorld [18], PDDL Planning, ScienceWorld [19]) and QA/web/tool-use (TriviaQA [20], WebWalkerQA [21], GAIA [22]), under three agent runners (Lobster, LangGraph [23], Microsoft Agent-Framework) and three LLM backbones (GPT-4.1-mini, Claude Sonnet-4, DeepSeek-V3.2); see Appendix A for benchmark sizes, framework descriptions, and the shared task-loader / tool / evaluation protocol. Beyond the no-memory ablation (Empty), we compare against nine memory baselines re-implemented on a shared retrieve/store interface, spanning vector-similarity, summarised-trajectory, LLM-reranked, insight-based, latent-token, and graph-structured designs [5, 7–10, 17, 24–26, 60]; for our reported M EM C ON numbers the wrapper is plugged into one fixed inner backend (G-Memory [9]) so every comparison shares the same storage layer (the wrapper is backend-agnostic, §3.3). Perbaseline mechanism descriptions and hyperparameter-search details are in Appendix A; numerical hyperparameter values are in Appendix C (Table 6). We report task success rate / answer accuracy as S/A (single deployment run per configuration, no seed averaging); per-task input tokens (Tok) are deferred to Appendix B. 4.2

Main Results

Table 1 reports S/A on the GPT-4.1-mini backbone in the main paper; per-backbone S/A tables for Sonnet-4 and DeepSeek-V3.2, together with the average per-task token cost, are deferred to Appendix B (Tables 3, 4, and 5). Figure 3 visualises the joint S/A vs. token-cost trade-off, and 7

DeepSeek V3.2 + LangGraph

GPT 4.1 mini backbone + Lobster

GAIA

Token Cost

Token Cost(K)

Token Cost(K)

Claude Sonnet 4 + Agent Framework

AFLWorld

PDDL

S/A(%)

Figure 3: Token cost vs. task success across memories. Each panel plots, for one (framework, benchmark) pair, every memory baseline as a bubble whose horizontal position is mean S/A (%), vertical position is mean per-task input tokens (in thousands or units), and area is proportional to per-task token cost. M EM C ON sits on the bottom-right of all three panels: it achieves the highest or near-highest S/A while using fewer tokens than every other memory.

Figure 2 traces two end-to-end episodes through the controller. We highlight four observations corresponding to Q1–Q4. (Q1) M EM C ON is consistently the strongest or near-strongest memory. On GPT-4.1-mini (Table 1), M EM C ON attains the top S/A on 4 of 6 benchmarks under Lobster, 2 under LangGraph, and 3 under Agent-FW, 9 of 18 cells overall, with concrete examples such as 67.9% ALFWorld (Lobster, the top score among all 10 memories), 40.0% PDDL (Agent-FW, +3.3 over the strongest fixedpipeline baseline in that cell), and 22.4–23.0% GAIA across frameworks against 16.4–21.2% for the rest. On Sonnet-4 (Table 3), where memory quality becomes decisive because the base model is strong enough to execute any sensible plan, M EM C ON is top S/A on 15 of 18 framework×benchmark cells, including the entire interactive block (e.g., 68.9% Lobster-PDDL vs. 67.0% best baseline and 18.0% no-memory; 67.1% Agent-FW-SciWorld vs. 66.0% best baseline and 17.0% no-memory). The three exceptions are narrow (≤ 0.4 points each). On DeepSeek-V3.2 (Table 4), M EM C ON is top S/A on all 9 interactive cells (e.g., 86.7% Lobster-ALFWorld vs. 84.3% next-best) and 15 of 18 cells overall; the GAIA column is the only one where another baseline occasionally edges M EM C ON by 0.3–0.4 points. Fixed-pipeline baselines are inconsistent across settings (some are strong on a few splits but catastrophically weak elsewhere), whereas M EM C ON is the only system that is uniformly top-1 or top-2 across all 54 cells. (Q2) Gains come with token savings, not extra retrieval. A naive explanation of M EM C ON’s accuracy gains would be “it retrieves more, hence uses more context.” Figure 3 and Table 5 refute this directly: on GPT-4.1-mini Lobster–ALFWorld, M EM C ON uses 39K tokens per task vs. 45K for the strongest fixed-pipeline baseline (−13%) while lifting S/A from 59.7% to 67.9%; on AgentFW–ALFWorld it uses 37K vs. 43K (−14%) at 69.4% S/A; on Sonnet-4 Agent-FW–PDDL it uses 60K vs. 67K (−10%) at 70.7% S/A; and on DeepSeek-V3.2 Lobster-ALFWorld it uses 57K vs. 67K (−15%) at 86.7% S/A. Across all three backbones we see simultaneous 5–20% token reductions and accuracy improvements, consistent with the policy learning to suppress retrieval when memory is sparse or irrelevant and to replace nearest-neighbour retrieval with plan injection when a distilled template already exists (§3.3). (Q3) Generalization to QA / web / tool-use benchmarks. M EM C ON is not specifically designed for question answering, yet the same controller yields improvements on TriviaQA, WebWalkerQA, and GAIA. On GPT-4.1-mini GAIA, M EM C ON reaches 22.4–23.0% across frameworks vs. 16.4–20.6% for the no-memory baseline and 20.0–21.2% for the strongest fixed-pipeline alternative. On Sonnet-4 GAIA, M EM C ON attains 27.5–28.9%, beating the next-best memory by 3–12 points. The relatively flat TriviaQA gaps (a short-answer benchmark where memory is inherently less important) serve as a sanity check that M EM C ON does not degrade easy settings while it lifts hard ones. (Q4) Backbone-robust gains, most pronounced under stronger LLMs. Across the three backbones the ordering is consistent: M EM C ON is competitive-to-dominant under GPT-4.1-mini, strictly dominant under DeepSeek-V3.2 (top S/A on every interactive cell), and most strongly differentiated under Sonnet-4 (top on 15/18). On Sonnet-4 Agent-FW, ALFWorld improves from an Empty baseline of 12.7% to 60.6% with M EM C ON, PDDL from 21.0% to 70.7%, and ScienceWorld from 17.0% to 67.1%. With stronger LLM execution, the binding constraint shifts from reasoning capability to whether the right experience is surfaced at the right time, which is precisely what M EM C ON’s adaptive controller addresses. Figure 2 illustrates this end-to-end on two qualitatively different queries: one where the controller starts in the cold phase and recovers via R E -R ETRIEVE, and one where a learned plan template lets P LAN I NJECT solve the task in a single pass. 8

S/A on GAIA S/A \& WebWalkerQA (\%) S/A on GAIA \& WebWalkerQA (\%) on GAIA \& WebWalkerQA (\%)

GAIA (filled per panel)

Learning rate α GAIA: best 23.0 @ α=0.15

WebWalkerQA

26

26 GAIA peak (0.15, 23.0)

24

GAIA peak default region Discount γ GAIA: best 23.0 @ γ∈{0.7, 0.9}

UCB constant c GAIA: best 23.0 @ c=1.4

Failure reward rfail GAIA: best 23.0 @ rfail = − 0.5

26 GAIA peak (1.4, 23.0)

24

26 GAIA peak (0.7, 23.0)

24

22

22

22

20

20

20

20

18

18

18

16

16

WW: 20.1

Learning rate0.2 α 0.1 0.3 GAIA: best 23.0 α@ α=0.15

WebWalkerQA

0.5 1.0 UCB constant c 1.5 c GAIA: best 23.0 @ c=1.4

0.4

26

18

16

WW: 19.8

GAIA (filled per panel)

2.0

WW: 19.6

GAIA peak

Discount 0.6 0.7 γ

0.5

default region

0.8

16

0.9

γ 23.0 @ γ∈{0.7, 0.9} GAIA: best

26 GAIA peak (0.15, 23.0)

GAIA peak (-0.5, 23.0)

24

22

WW: 19.2

−1.50 −1.25 −1.00 −0.75 −0.50 −0.25 Failure reward rfail 0.00

26 GAIA peak (1.4, 23.0)

GAIA:rfail best 23.0 @ rfail = − 0.5

26 GAIA peak (0.7, 23.0)

Figure 4: Single-knob sensitivity (continuous policy hyperparameters). Each panel sweeps one knob, Efficiency weight λ 24

24

24

24

GAIA peak (-0.5, 23.0)

Action preset 22 GAIA: best 23.0 @ default

S/A on GAIA \& WebWalkerQA (\%)

22 22 GAIA: best 23.0 α, @ λ=0.3 learning rate UCB constant c, discount γ, and failure reward rfail , while keeping all others22 at their defaults 20 20 20 (Table 6). The solid coloured line20 is GAIA S/A (%), the grey dashed line is WebWalkerQA, the tan band marks 18 18 the18 default region, and the ⋆ marks the GAIA peak. M EM C18ON is robust over a wide region around each 16 16 16 default: GAIA S/A stays within ±2.5 points of the peak across 16the entire scanned range for every knob, and the 0.1 0.2 0.3 0.4 0.5 1.0 1.5 2.0 0.5 0.6 0.7 0.8 0.9 −1.50 −1.25 −1.00 −0.75 −0.50 −0.25 0.00 optimum coincides with the default for α, c, and rfail (with γ ∈ {0.7, 0.9} tied within 0.1 point). Backbone is γ α c r GPT-4.1-mini on Lobster. 26

26

GAIA peak (0.3, 23.0)

24

24

22

WW: 20.1

20

GAIA peak (default, 23.0)

23.0

21.8

22

20.1

20

18

20.6

WW: 19.8

20.6

19.9

WW: 19.6

WW: 19.2

19.5

19.1

fail

18

16

16

WW: 19.5

0.0

0.2

0.4

0.6

WW: 19.6

0.8

default

λ λ Efficiency weight GAIA: best 23.0 @ λ=0.3 26

26 GAIA peak (0.3, 23.0)

24

24

22

22

20

20

18

18

16

WW: 19.5

0.0

0.2

0.4

retrieval heavy

plan first

compact

Variant

Action preset preset GAIA: best 23.0 @ default

0.6

λ

0.8

GAIA peak (default, 23.0) 23.0 21.8 20.1

20.6 19.9

19.1

16

20.6 19.5

Static backend + learned UCB + plan injection (g) + goal decomposition + all (= M EM C ON)

ALFWorld GAIA 59.7 64.9 66.4 67.2 67.9

21.2 22.4 22.4 22.4 22.4

WW: 19.6

default

retrieval heavy

plan first

compact

preset

Figure 5: Single-knob sensitivity (efficiency weight λ & action-preset). Left: sweeping the efficiency-bonus weight λ shows that GAIA peaks at the default λ = 0.3; both removing the bonus (λ = 0) and over-weighting it (λ ≥ 0.5) hurt by ∼2 points. Right: swapping the default 9-action preset for hand-tuned alternatives (retrieval heavy, plan first, compact); the default preset is the best on average.

Table 2: Component ablation on GPT-4.1mini. We turn off each M EM C ON component and measure GAIA S/A and LobsterALFWorld success. The learned UCB controller is the largest single contributor; both augmented operations help additionally. Numbers are S/A (%); “∆” is the drop from the full M EM C ON configuration.

Overall, these results support the central claim of the paper: replacing a fixed memory pipeline with a lightweight learned controller yields consistent, framework-/benchmark-/backbone-agnostic accuracy gains, and does so with fewer rather than more tokens. 4.3

Ablation

We probe two questions: (i) how sensitive is M EM C ON to each policy hyperparameter, and (ii) how much of M EM C ON’s gain over the underlying static-pipeline backend comes from the learned controller versus the two augmented memory operations of §3.3? We answer (i) with a single-knob sweep (Figures 4–5) and (ii) with a four-row component ablation (Table 4). The component ablation (Table 4) addresses a confound flagged in earlier reviews: most of the GPT-4.1-mini Lobster-ALFWorld gain over the static-pipeline backend is attributable to the learned UCB controller (+5.2 S/A) rather than to the two augmented operations (+1.5 each). On GAIA, which contains no composite goals of the form targeted by goal decomposition, only the learned controller contributes (+1.2 S/A); the augmented operations add no accuracy because they simply have no opportunity to fire. This confirms that the central methodological contribution (learning when, what, and how much to retrieve) is the dominant source of the empirical gains, and that the augmented operations are useful but optional add-ons whose benefit is restricted to environments with structured composite goals.

5

Conclusion

We introduced M EM C ON, a backend-agnostic framework that treats agent memory not as a fixed retrieval pipeline, but as a controlled decision process. By modeling memory operations as actions in a Memory MDP and learning a lightweight online UCB policy, M EM C ON adaptively decides when to 9

retrieve, reuse plans, re-retrieve, consolidate, or skip memory access without requiring pretraining or additional LLM calls. Across interactive, QA, web, and tool-use benchmarks, M EM C ON consistently improves task success across multiple agent frameworks and LLM backbones while also reducing token consumption. These results suggest that effective long-term memory for LLM agents depends not only on what is stored, but also on learning how memory should be accessed and managed over time.

References [1] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. ReAct: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023. [2] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Advances in Neural Information Processing Systems (NeurIPS), 2023. [3] Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, Wayne Xin Zhao, Zhewei Wei, and Jirong Wen. A survey on large language model based autonomous agents. Frontiers of Computer Science, 2024. [4] Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, et al. The rise and potential of large language model based agents: A survey. arXiv preprint arXiv:2309.07864, 2023. [5] Joon Sung Park, Joseph C. O’Brien, Carrie J. Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. Generative agents: Interactive simulacra of human behavior. In ACM Symposium on User Interface Software and Technology (UIST), 2023. [6] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2023. [7] Andrew Zhao, Daniel Huang, Quentin Xu, Matthieu Lin, Yong-Jin Liu, and Gao Huang. ExpeL: LLM agents are experiential learners. 2024. [8] Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. 2024. [9] Guibin Zhang, Muxin Yue, Xiangguo Li, Jiaxuan Ran, Rui Song, Ran Cheng, Zheng Wang, and Shirui Pan. G-Memory: Tracing hierarchical memory for multi-agent systems. arXiv preprint arXiv:2506.07398, 2025. [10] Haoran Ou, Jianyu Li, Weiran Chen, Yuxin Liu, Ting Sun, and Dian Yu. Latent memory: Distilling cross-task experience into learnable tokens for language agents. arXiv preprint arXiv:2509.18432, 2025. [11] Charles Packer, Sarah Wooders, Kevin Lin, Vivian Fang, Shishir G. Patil, Ion Stoica, and Joseph E. Gonzalez. MemGPT: Towards llms as operating systems. arXiv preprint arXiv:2310.08560, 2023. [12] Prateek Chhikara, Deshraj Khant, Saket Aryan, Taranjeet Singh, and Deepak Yadav. Mem0: Building production-ready ai agents with scalable long-term memory. arXiv preprint arXiv:2504.19413, 2025. [13] Bingbing Wu, Xian Yang, Xinyan Chen, Jiayin Liu, Haowen Li, Yu Su, and Yu Zhang. MemP: Procedural memory from trajectories for language agents. arXiv preprint arXiv:2508.06433, 2025. [14] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235–256, 2002. 10

[15] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandit approach to personalized news article recommendation. In International Conference on World Wide Web (WWW), 2010. [16] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2nd edition, 2018. [17] Wanjun Zhong, Lianghong Guo, Qiqi Gao, He Ye, and Yanlin Wang. MemoryBank: Enhancing large language models with long-term memory. 2024. [18] Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. ALFWorld: Aligning text and embodied environments for interactive learning. In International Conference on Learning Representations (ICLR), 2021. [19] Ruoyao Wang, Peter Jansen, Marc-Alexandre Côté, and Prithviraj Ammanabrolu. ScienceWorld: Is your agent smarter than a 5th grader? In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2022. [20] Mandar Joshi, Eunsol Choi, Daniel S. Weld, and Luke Zettlemoyer. TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension. In Annual Meeting of the Association for Computational Linguistics (ACL), 2017. [21] Jialong Wu, Wenbiao Yin, Yong Jiang, Zhenglin Wang, Zekun Xi, Runnan Fang, Linhai Zhang, Yulan He, Deyu Zhou, Pengjun Xie, and Fei Huang. WebWalker: Benchmarking llms in web traversal. arXiv preprint arXiv:2501.07572, 2025. [22] Grégoire Mialon, Clémentine Fourrier, Craig Swift, Thomas Wolf, Yann LeCun, and Thomas Scialom. GAIA: A benchmark for general ai assistants. arXiv preprint arXiv:2311.12983, 2023. [23] Harrison Chase and LangChain Team. LangGraph: Controllable cognitive architectures for agentic applications. 2024. [24] Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, Lingfeng Xiao, Chenglin Wu, and Jürgen Schmidhuber. MetaGPT: Meta programming for a multi-agent collaborative framework. In International Conference on Learning Representations (ICLR), 2024. [25] Chen Qian, Wei Liu, Hongzhang Liu, Nuo Chen, Yufan Dang, Jiahao Li, Cheng Yang, Weize Chen, Yusheng Su, Xin Cong, Juyuan Xu, Dahai Li, Zhiyuan Liu, and Maosong Sun. ChatDev: Communicative agents for software development. In Annual Meeting of the Association for Computational Linguistics (ACL), 2024. [26] Chen Qian, Yaxi Wang, Zhouyi Wang, Weize Chen, Yufan Zhou, Ran Yu, Chen Zhou, Zhiyuan Liu, and Maosong Sun. OAgents: Open-source agents toward reliable experiential learning. arXiv preprint arXiv:2506.13815, 2025. [27] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Marc Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value-decomposition networks for cooperative multi-agent learning based on team reward. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018. [28] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder de Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning (ICML), 2018. [29] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-competitive environments. In Advances in Neural Information Processing Systems (NeurIPS), 2017. [30] Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI Conference on Artificial Intelligence, 2018. 11

[31] Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of PPO in cooperative multi-agent games. 2022. [32] Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip H. S. Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the StarCraft multi-agent challenge? arXiv preprint arXiv:2011.09533, 2020. [33] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philip H. S. Torr, Jakob Foerster, and Shimon Whiteson. The StarCraft multi-agent challenge. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2019. [34] Jakob N. Foerster, Yannis M. Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2016. [35] Muning Wen, Jakub Grudzien Kuba, Runji Lin, Weinan Zhang, Ying Wen, Jun Wang, and Yaodong Yang. Multi-agent reinforcement learning is a sequence modeling problem. In Advances in Neural Information Processing Systems (NeurIPS), 2022. [36] Sven Gronauer and Klaus Diepold. Multi-agent deep reinforcement learning: A survey. Artificial Intelligence Review, 55:895–943, 2022. [37] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321–384, 2021. [38] Pablo Hernandez-Leal, Bilal Kartal, and Matthew E. Taylor. A survey and critique of multiagent deep reinforcement learning. Autonomous Agents and Multi-Agent Systems, 33:750–797, 2019. [39] Yan Meng, Sen Liu, Li Zhang, and Hang Xu. LLM-augmented multi-agent reinforcement learning for collaborative task allocation. arXiv preprint arXiv:2403.08282, 2024. [40] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. 2020. [41] Christopher J. C. H. Watkins and Peter Dayan. Q-learning. In Machine Learning, volume 8, pages 279–292, 1992. [42] Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Beibin Li, Erkang Zhu, Li Jiang, Xiaoyun Zhang, Shaokun Zhang, Jiale Liu, Ahmed Hassan Awadallah, Ryen W. White, Doug Burger, and Chi Wang. AutoGen: Enabling next-gen llm applications via multi-agent conversation. arXiv preprint arXiv:2308.08155, 2023. [43] Guohao Li, Hasan Abed Al Kader Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. CAMEL: Communicative agents for “mind” exploration of large language model society. In Advances in Neural Information Processing Systems (NeurIPS), 2023. [44] Weize Chen, Yusheng Su, Jingwei Zuo, Cheng Yang, Chenfei Yuan, Chi-Min Chan, Heyang Yu, Yaxi Lu, Yi-Hsin Hung, Chen Qian, Yujia Qin, Xin Cong, Ruobing Xie, Zhiyuan Liu, Maosong Sun, and Jie Zhou. AgentVerse: Facilitating multi-agent collaboration and exploring emergent behaviors. In International Conference on Learning Representations (ICLR), 2024. [45] Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate. In International Conference on Machine Learning (ICML), 2024. [46] Tian Liang, Zhiwei He, Wenxiang Jiao, Xing Wang, Yan Wang, Rui Wang, Yujiu Yang, Zhaopeng Tu, and Shuming Shi. Encouraging divergent thinking in large language models through multi-agent debate. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2024. [47] Mingchen Zhuge, Haozhe Liu, Francesco Faccio, Dylan R. Ashley, Róbert Csordás, Anand Gopalakrishnan, Abdullah Hamdi, Hasan Abed Al Kader Hammoud, Vincent Herrmann, Kazuki Irie, et al. Mindstorms in natural language-based societies of mind. arXiv preprint arXiv:2305.17066, 2023. 12

[48] Rui Hao, Linmei Hu, Weijian Qi, Qingliu Wu, Yirui Zhang, and Liqiang Nie. ChatLLM network: More brains, more intelligence. 2023. [49] Zijun Liu, Yanzhe Zhang, Peng Li, Yang Liu, and Diyi Yang. Dynamic LLM-agent network: An LLM-agent collaboration framework with agent team optimization. In Conference on Language Modeling (COLM), 2024. [50] Mingchen Zhuge, Wenyi Wang, Louis Kirsch, Francesco Faccio, Dmitrii Khizbullin, and Jürgen Schmidhuber. GPTSwarm: Language agents as optimizable graphs. 2024. [51] Taicheng Guo, Xiuying Chen, Yaqi Wang, Ruidi Chang, Shichao Pei, Nitesh V. Chawla, Olaf Wiest, and Xiangliang Zhang. Large language model based multi-agents: A survey of progress and challenges. International Joint Conference on Artificial Intelligence (IJCAI), 2024. [52] Yashar Talebirad and Amirhossein Nadiri. Multi-agent collaboration: Harnessing the power of intelligent LLM agents. arXiv preprint arXiv:2306.03314, 2023. [53] Ali Modarressi, Abdullatif Köksal, Ayyoob Imani, Mohsen Fayyaz, and Hinrich Schütze. MemLLM: Finetuning llms to use an explicit read-write memory. arXiv preprint arXiv:2404.11672, 2024. [54] Lei Liu, Xiaoyan Yang, Yue Shen, Binbin Hu, Zhiqiang Zhang, Jinjie Gu, and Guannan Zhang. Think-in-memory: Recalling and post-thinking enable llms with long-term memory. arXiv preprint arXiv:2311.08719, 2023. [55] Aman Madaan, Niket Tandon, Peter Clark, and Yiming Yang. Memory-assisted prompt editing to improve gpt-3 after deployment. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2022. [56] Zora Zhiruo Wang, Jiayuan Mao, Daniel Fried, and Graham Neubig. Agent workflow memory. arXiv preprint arXiv:2409.07429, 2024. [57] Qirui Mi, Zhijian Ma, Mengyue Yang, Haoxuan Li, Yisen Wang, Haifeng Zhang, and Jun Wang. Procmem: Learning reusable procedural memory from experience via non-parametric ppo for llm agents. arXiv preprint arXiv:2602.01869, 2025. [58] Haozhen Zhang, Quanyu Long, Jianzhu Bao, Tao Feng, Weizhi Zhang, Haodong Yue, and Wenya Wang. Memskill: Learning and evolving memory skills for self-evolving agents. arXiv preprint arXiv:2602.02474, 2025. [59] Mengkang Hu, Tianxing Chen, Qiguang Zou, Yuheng Liu, Yuxi Sun, Fei Mi, Yitao Liang, Jie Fu, and Yuanjing Mao. HiAgent: Hierarchical working memory management for long-horizon agent tasks. arXiv preprint arXiv:2408.09559, 2024. [60] Bodhisattwa Prasad Majumder, Bhavana Dalvi, Peter Jansen, Oyvind Tafjord, Niket Tandon, Li Zhang, Chris Callison-Burch, and Peter Clark. CLIN: A continually learning language agent for rapid task adaptation and generalization. In Conference on Language Modeling (COLM), 2024. [61] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmented generation for knowledge-intensive NLP tasks. In Advances in Neural Information Processing Systems (NeurIPS), 2020. [62] Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020. [63] Akari Asai, Zeqiu Wu, Yizhong Wang, Avirup Sil, and Hannaneh Hajishirzi. Self-RAG: Learning to retrieve, generate, and critique through self-reflection. 2024. [64] Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. PlanBench: An extensible benchmark for evaluating large language models on planning and reasoning about change. 2023. 13

[65] Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. LLM+P: Empowering large language models with optimal planning proficiency. arXiv preprint arXiv:2304.11477, 2023. [66] Malte Helmert. The fast downward planning system. Journal of Artificial Intelligence Research (JAIR), 26:191–246, 2006.

14

A

Experimental Setup Details

This appendix expands the abbreviated description in §4.1 with full benchmark sizes, framework descriptions, baseline mechanisms, and the hyperparameter-search protocol. A.1

Benchmarks

Interactive decision-making (long-horizon, multi-step). ALFWorld [18] contains 134 household tasks across 6 types (put, clean, heat, cool, examine, puttwo); it couples a TextWorld front-end with embodied AI2-THOR back-ends. PDDL Planning consists of 100 classical planning tasks spanning blocksworld, barman, gripper, tyreworld, closely related to PlanBench [64–66]. ScienceWorld [19] contains 100 elementary-science experimental tasks (boiling water, melting ice, finding animals by property, etc.). Knowledge / web / tool-use QA. TriviaQA [20] (200 questions, short-answer open-domain QA); WebWalkerQA [21] (200 multi-hop web traversal questions requiring site navigation and information extraction); GAIA [22] (165 general-AI-assistant questions spanning tool use, web search, and document reading). A.2

Agent Frameworks

We use three architecturally distinct agent runners, each sharing identical task loaders, tools, and evaluation protocol so that the only varying factor across baselines is the memory system: Lobster, a singleagent minimalist runner that talks to the OpenAI-compatible chat API directly; LangGraph [23], a graph-structured multi-agent workflow built on LangChain; and Microsoft Agent-Framework, a pipeline-based multi-agent system. All experiments use a 30-step horizon for interactive tasks and the benchmark-default budget for QA, with the same temperature and tool protocol across memory baselines. A.3

Memory Baselines

Beyond the no-memory ablation (Empty), we compare against nine memory systems re-implemented on a shared two-method (retrieve/store) interface so that differences are purely algorithmic rather than due to prompt or I/O variation: (1) MetaGPT [24]: pure vector similarity retrieval over stored trajectories, no LLM calls at retrieval time; (2) Voyager [8]: LLM summarises each trajectory before storage, retrieval by cosine similarity over summarised embeddings; (3) Generative [5]: retrieves candidate trajectories and uses an LLM to re-rank them by estimated relevance; (4) ChatDev [25]: periodic LLM-driven phase-based summarisation every 10 steps; no cross-task retrieval; (5) MemoryBank [17]: temporal-decay memory with Ebbinghaus-style exponential forgetting on top of vector retrieval; (6) OAgents [26]: insight-based learning that compares paired successful/failed trials to distil and edit natural-language rules; (7) ExperienceBank: LLM-scored relevance retrieval with generative re-ranking over an explicit experience bank [7, 60]; (8) LatentMem [10]: distils cross-task experience into a small bank of learnable latent tokens, paired with a graph-based retrieval front-end and LatentMem-specific insight prompts; (9) G-Memory [9]: a graph-structured memory combining vector retrieval, a task graph with k-hop traversal, and scored insight rules with periodic LLM-driven merge. For our reported M EM C ON numbers we plug the wrapper into one specific backend (G-Memory) so that every M EM C ON–baseline comparison is held fixed at the inner storage layer; because the wrapper is backend-agnostic (§3.3), it could equally be composed with any of the other eight, and we expect the qualitative trend (controller adds adaptivity at zero LLM cost) to transfer. A.4

Hyperparameter Selection Protocol

M EM C ON uses the default 9-action set (§3.1), warm-start enabled with the priors of §3.2, and the reward shape of Eq. (5). The three policy hyperparameters (α, γ, c) are selected per backbone via a small grid search on a held-out 30-task subset of ALFWorld (Lobster), independent of the evaluation tasks; warm-start priors, reward constants, and discretisation thresholds are fixed across backbones. All numerical values are listed in Appendix C (Table 6). The Q-table and success-plan index are 15

persisted to disk and reloaded across runs; experiments use a single realistic deployment run per configuration (no seed averaging) to reflect the online setting.

B

Per-Backbone S/A Tables and Token Cost

This appendix reports the full per-backbone S/A tables for the two backbones omitted from the main paper (Claude Sonnet-4 and DeepSeek-V3.2) and provides the average per-task token cost (Tok) accompanying each S/A entry, for all three backbones.

B.1

Claude Sonnet-4 (S/A only)

Interactive (S/A %) Framework Memory

QA (S/A %)

Avg.

ALFWorld PDDL SciWorld TriviaQA WebWalkerQA GAIA

Lobster

Empty G-Memory MetaGPT Voyager Generative ChatDev MemoryBank OAgent ExpBank LatentMem M EM C ON

14.2 31.3 6.7 10.4 6.7 11.9 9.0 28.4 5.2 30.6 32.3

18.0 58.0 8.0 14.0 15.0 17.0 12.0 42.0 11.0 67.0 68.9

19.0 25.0 12.0 10.0 15.0 14.0 8.0 27.0 5.0 82.0 81.6

81.5 82.0 82.5 81.5 81.5 81.5 81.5 81.5 81.5 81.5 84.4

17.1 16.3 15.9 16.7 16.4 16.6 16.5 17.4 16.2 15.8 19.4

24.2 20.6 24.9 24.9 25.4 26.7 22.4 24.2 23.6 17.6 27.5

29.0 38.9 25.0 26.3 26.7 28.0 24.9 36.8 23.8 49.1 52.4

LangGraph

Empty G-Memory MetaGPT Voyager Generative ChatDev MemoryBank OAgent ExpBank LatentMem M EM C ON

17.2 46.3 16.4 22.4 17.9 12.7 26.9 53.0 17.9 53.7 55.4

15.0 33.0 24.0 22.0 26.0 28.0 25.0 33.0 22.0 61.0 63.2

20.0 37.0 21.0 33.0 31.0 20.0 39.0 58.0 21.0 68.0 69.3

82.5 81.5 83.0 82.5 82.0 82.5 82.0 80.5 82.0 82.5 82.8

15.9 17.4 15.4 17.1 16.6 16.1 15.8 16.9 16.3 18.0 19.2

25.4 19.4 23.0 25.4 21.8 22.4 22.4 17.6 23.0 23.0 28.0

29.3 39.1 30.5 33.7 32.6 30.3 35.2 43.2 30.4 51.0 53.0

Agent-FW

Empty G-Memory MetaGPT Voyager Generative ChatDev MemoryBank OAgent ExpBank LatentMem M EM C ON

12.7 20.9 15.7 10.4 20.2 12.7 11.9 23.9 6.0 58.2 60.6

21.0 23.0 19.0 14.0 20.0 16.0 20.0 30.0 6.0 70.0 70.7

17.0 33.0 19.0 14.0 26.0 19.0 20.0 28.0 7.0 66.0 67.1

83.0 81.5 81.0 81.0 82.0 82.0 81.5 81.5 82.0 81.5 84.3

17.1 17.5 17.5 9.5 17.2 15.6 17.5 10.2 16.4 15.1 17.1

21.8 18.8 23.6 24.9 26.1 22.4 23.6 23.6 24.2 16.4 28.9

28.8 32.5 29.3 25.6 31.9 28.0 29.1 32.9 23.6 51.2 54.8

Table 3: Sonnet-4 backbone. S/A (%) on the same six benchmarks and ten memory baselines as Table 1. Avg. is the arithmetic mean across the six benchmarks. Bold: highest S/A per column within each framework block (ties bolded). Underline: second-best S/A per column within each framework block. M EM C ON rows shaded in green. M EM C ON attains the top S/A on 15 of 18 framework×benchmark cells (and the highest Avg. in every framework); the three exceptions are Lobster–ScienceWorld (LatentMem 82.0 vs. M EM C ON 81.6), LangGraph– TriviaQA (MetaGPT 83.0 vs. M EM C ON 82.8), and Agent-FW–WebWalkerQA (G-Mem/MetaGPT/MemoryBank tied at 17.5 vs. M EM C ON 17.1).

16

Interactive (S/A %) Framework Memory

QA (S/A %)

Avg.

ALFWorld PDDL SciWorld TriviaQA WebWalkerQA GAIA

Lobster

Empty G-Memory MetaGPT Voyager Generative ChatDev MemoryBank OAgent ExpBank LatentMem M EM C ON

64.2 79.8 75.4 84.3 82.8 64.9 81.3 82.8 76.9 77.6 86.7

63.0 69.0 73.0 78.0 79.0 69.0 81.0 76.0 73.0 72.0 83.6

67.0 77.0 76.0 86.0 88.0 69.0 84.0 84.0 78.0 80.0 90.2

75.5 73.5 73.0 72.0 73.5 71.5 75.5 67.0 75.0 71.0 77.8

17.6 18.5 18.0 19.0 21.0 19.0 20.1 17.2 18.5 17.2 22.0

28.5 24.9 27.9 27.3 25.4 29.1 27.3 27.3 26.7 29.9 29.6

52.6 57.1 57.2 61.1 61.6 53.8 61.5 59.1 58.0 58.0 65.0

LangGraph

Empty G-Memory MetaGPT Voyager Generative ChatDev MemoryBank OAgent ExpBank LatentMem M EM C ON

66.4 84.3 88.8 80.6 79.8 64.2 84.3 88.8 82.1 86.6 89.8

63.0 79.0 75.0 74.0 68.0 71.0 80.0 79.0 70.0 74.0 82.2

66.0 83.0 85.0 80.0 80.0 62.0 88.0 91.0 78.0 85.0 94.0

71.5 71.5 72.5 73.5 71.5 76.0 70.5 69.5 72.5 70.5 77.5

18.9 16.4 19.3 18.1 19.5 19.4 17.2 18.1 17.7 17.9 22.5

21.8 29.1 30.3 27.3 26.1 28.5 28.5 26.7 28.5 33.1 32.8

51.3 60.6 61.8 58.9 57.5 53.5 61.4 62.2 58.1 61.2 66.5

Agent-FW

Empty G-Memory MetaGPT Voyager Generative ChatDev MemoryBank OAgent ExpBank LatentMem M EM C ON

62.7 77.6 81.3 81.3 80.6 61.9 82.8 82.1 80.6 83.6 85.4

68.0 69.0 75.0 83.0 80.0 63.0 83.0 74.0 82.0 76.0 84.2

68.0 80.0 83.0 86.0 83.0 65.0 88.0 85.0 87.0 89.0 91.3

72.0 71.0 75.0 73.5 74.0 73.5 74.0 74.5 72.5 75.0 77.8

19.9 20.5 17.9 18.1 18.6 18.3 19.4 16.6 19.1 16.4 21.5

27.3 15.8 24.9 27.3 24.9 17.0 27.9 25.4 25.4 31.4 31.0

53.0 55.7 59.5 61.5 60.2 49.8 62.5 59.6 61.1 61.9 65.2

Table 4: DeepSeek-V3.2 backbone. Same benchmarks and baselines as Table 1. Avg. is the arithmetic mean across the six benchmarks. Bold: highest S/A per column within each framework block (ties bolded). Underline: second-best S/A per column within each framework block. M EM C ON rows shaded in green. M EM C ON attains the top S/A on all nine interactive cells and on 15 of 18 cells overall; the three GAIA exceptions all go to LatentMem.

B.2

DeepSeek-V3.2 (S/A only)

B.3

Token Cost (Tok per task)

Table 5 reports the average number of LLM-input tokens consumed per task for the GPT-4.1-mini main results (numbers for the other two backbones are available in the released code; trends are qualitatively identical). The token-cost vs. S/A trade-off is summarized visually in Figure 3 of the main paper.

C

Hyperparameters and Implementation Details

This appendix lists the full set of hyperparameters used by M EM C ON across all experiments. Table 6 consolidates every numeric constant referenced in §3–§4 into one place; Table 7 gives the structural action set A which has a different layout. All values are taken directly from the released implementation, and the same defaults are used for every number reported in the main paper unless otherwise noted. 17

Interactive (Tok) Framework Memory

QA (Tok)

Avg.

ALFWorld PDDL SciWorld TriviaQA WebWalkerQA GAIA

Lobster

Empty G-Memory MetaGPT Voyager Generative ChatDev MemoryBank OAgent ExpBank M EM C ON

44K 45K 48K 48K 48K 49K 44K 52K 44K 39K

98K 155K 154K 154K 148K 102K 143K 162K 154K 148K

31K 44K 33K 39K 34K 32K 38K 36K 44K 31K

58 288 57 56 57 57 57 146 57 58

153 459 157 154 155 153 151 244 154 164

377 703 421 407 382 395 404 566 399 440

29K 41K 39K 40K 38K 31K 38K 42K 40K 36K

LangGraph

Empty G-Memory MetaGPT Voyager Generative ChatDev MemoryBank OAgent ExpBank M EM C ON

51K 42K 49K 47K 49K 46K 47K 51K 45K 41K

101K 157K 156K 145K 154K 100K 137K 161K 160K 142K

31K 42K 41K 38K 42K 33K 36K 38K 42K 32K

57 267 57 57 57 56 57 242 57 61

152 434 156 155 154 154 154 309 154 172

406 720 398 387 384 411 410 477 395 456

31K 40K 41K 38K 41K 30K 37K 42K 41K 36K

Agent-FW

Empty G-Memory MetaGPT Voyager Generative ChatDev MemoryBank OAgent ExpBank M EM C ON

46K 43K 46K 49K 49K 49K 42K 44K 46K 37K

102K 154K 168K 140K 164K 100K 143K 157K 158K 111K

33K 41K 37K 37K 39K 32K 44K 38K 38K 33K

57 300 57 57 56 56 57 222 56 56

154 428 152 152 150 152 151 236 154 186

407 691 407 411 356 405 389 470 393 462

30K 40K 42K 38K 42K 30K 38K 40K 40K 30K

Table 5: Token cost on GPT-4.1-mini (average input tokens per task; K = thousand). Avg. is the arithmetic mean across the six benchmarks (in K). Bold: lowest Tok per column within each framework block (ties bolded). Underline: second-lowest per column within each framework block. M EM C ON rows shaded in green; M EM C ON achieves the lowest token cost on Lobster–ALFWorld, LangGraph–ALFWorld, and Agent-FW–ALFWorld while attaining the highest S/A in those cells (cf. Table 1), and ties for the lowest Avg. on Agent-FW.

Discretised state key.

The MDP state key used by the controller is

ϕ(s) = ⟨ goal type, step phase, is stuck, min(hold, 2), min(⌊visited/3⌋, 4), min(⌊mem size/10⌋, 5), plan available, learning phase ⟩.

(8)

with the bin definitions in Table 6. This coarse discretisation yields on the order of a few hundred distinct state keys per benchmark and enables tabular learning in tens of tasks. Action space. Table 7 lists the structural action set A used in all main-paper experiments (preset "default"). Additional presets ("retrieval heavy", "plan first", "compact") are available in the released code; the action-preset ablation in §4.3 (right panel of Figure 5) shows that the default preset wins on both QA benchmarks. LLM, agent framework, and benchmark settings. Agent frameworks use their default configurations, modified only to share identical task loaders and evaluators. Interactive benchmarks: ALFWorld (134 tasks, 6 types), PDDL (100 tasks across blocksworld/barman/gripper/tyreworld), ScienceWorld (100 tasks). QA benchmarks: TriviaQA (200 questions), WebWalkerQA (200), GAIA (165). Each reported number is a single realistic deployment run, with the Q-table persisted across tasks; LLM temperature, run protocol, and seed handling follow the values listed in Table 6. 18

Table 6: Complete list of M EM C ON hyperparameters used in all reported experiments. The four groups—policy, warm-start priors, reward shape, and state discretisation/runtime—contain every numeric constant referenced anywhere in the paper. Policy hyperparameters (α, γ, c) are selected per backbone via a small grid search on a held-out 30-task ALFWorld split (Lobster); all other constants are shared across backbones. Symbol

GPT-4.1-mini

Sonnet-4

DeepSeekV3.2

Description

Policy hyperparameters (per backbone, used in Eqs. (6), (25)) α (step size) 0.15 0.12 0.18 γ (discount) 0.9 0.92 0.88 c (UCB coeff.) warm-start

1.4 enabled

1.2 enabled

Q-learning step size Within-episode discount factor for reverse credit assignment UCB exploration coefficient Initialise unseen (s, a) with priors below

1.6 enabled

Warm-start priors Q0 (s, a) for unseen (s, a) (same across backbones) R ETRIEVE +0.5 P LAN I NJECT +0.3 R E -R ETRIEVE +0.1 C ONSOLIDATE 0.0 F ORGET −0.1 NOOP −0.2

retrieval is usually helpful plans help when available useful only when stuck neutral mildly risky doing nothing usually hurts

Reward shape (Eq. (5)) rsucc rfail λ Tmax

1.0 0.5 0.3 30 steps (interactive); benchmark default (QA)

success bonus failure penalty (subtracted) efficiency-bonus weight step horizon

State discretisation bins ϕ(s) (used in ϕ for tabular Q) early (< 8), mid (8–17), late (≥ 18) step phase learning phase cold (task index ≤ 15); warm (task index > 15) is stuck trigger 2 consecutive identical actions held-objects bin min(hold, 2) locations bin min(⌊visited/3⌋, 4) mem-size bin min(⌊mem size/10⌋, 5)

step-count bin for stask task-index bin for smem sets the stuck flag cap on objects-held count coarse unique-location bin coarse memory-size bin

Persistence and runtime persist path flush interval LLM temperature seed averaging

Q-table file Q-table write frequency sampling temperature matches online-deployment setting

./memcon/policy q.json every 5 updates 0 (interactive); benchmark default (QA) none (single deployment run per cell)

Table 7: Default action space A used in all main-paper experiments. Backends that do not implement maintenance hooks silently no-op on C ONSOLIDATE/F ORGET (§3.3).

D

Idx

Operation

0 1 2 3 4 5 6 7 8

R ETRIEVE (shallow) R ETRIEVE (medium) R ETRIEVE (deep) P LAN I NJECT R E -R ETRIEVE (alt. query) C ONSOLIDATE F ORGET R ETRIEVE (insight-only) NOOP

top k

insight k

hop

1 2 3 1 2 – – 1 –

3 5 8 3 5 – – 2 –

1 1 2 – 2 – – 0 –

Theoretical Justification

This appendix formalizes and proves the learning guarantees of M EM C ON. We show that (i) the Memory MDP decomposes into a family of per-state stochastic bandits (Lemma D.6); (ii) the UCB rule used in M EM C ON admits a sub-Gaussian concentration inequality (Lemma D.7) yielding an O(log n) per-state regret (Theorem D.8) and an O(|Φ||A| log T ) global regret (Corollary D.9); (iii) the reverse-discounted Q-update is a Robbins–Monro stochastic approximation whose iterates 19

converge almost surely (Theorem D.13) and in L2 (Proposition D.15) to the true action value; and (iv) the greedy policy extracted from Q is asymptotically optimal (Theorem D.18). All results are stated and proved from first principles; standard references are [14–16, 40]. D.1

Preliminaries and Notation

Definition D.1 (Memory MDP). The Memory MDP of M EM C ON is the tuple Mmem = (S, A, T , R, γ) with finite discretized state space Φ := ϕ(S), finite action space A with |A| = 9, deterministic (but black-box) transition T : Φ × A → Φ, bounded reward kernel R : Φ × A → P([rmin , rmax ]) with rmin = −0.5 and rmax = rsucc + λ = 1.3, and within-episode discount γ = 0.9. Definition D.2 (Per-state arm distribution). For each (ϕ, a) ∈ Φ × A, let   Dϕ,a := Law γ |ep|−j−1 · ri ϕj = ϕ, aj = a , µ(ϕ, a) := EG∼Dϕ,a [G]. Let a⋆ (ϕ) := arg maxa∈A µ(ϕ, a) be the optimal arm at ϕ, and define the sub-optimality gap ∆(ϕ, a) := µ(ϕ, a⋆ (ϕ)) − µ(ϕ, a) ≥ 0,

∆min := min

min

ϕ∈Φ a:∆(ϕ,a)>0

∆(ϕ, a).

Assumption D.3 (Conditional stationarity). For every (ϕ, a) ∈ Φ × A, the distribution Dϕ,a is time-invariant, and draws across episodes are conditionally independent given (ϕ, a). Assumption D.4 (Bounded reward). Every draw G ∼ Dϕ,a satisfies G ∈ [Gmin , Gmax ] ⊂ R with W := Gmax − Gmin ≤ rmax − γ |ep|−1 rmin ≤ 1.8. (t)

Definition D.5 (Visit counts, empirical mean, pseudo-regret). Write Na (ϕ) for the number of times P (t) action a was taken at ϕ through decision t, and N (t) (ϕ) := a∈A Na (ϕ). The empirical mean of (t) arm (ϕ, a) after Na (ϕ) pulls is µ̂t (ϕ, a) :=

1

X

(t) Na (ϕ) s≤t: ϕs =ϕ, as =a

Gs .

The per-state pseudo-regret after n pulls at ϕ is Rn (ϕ) := n · µ(ϕ, a⋆ (ϕ)) −

n X

µ(ϕ, at ) =

t=1

Na(n) (ϕ) ∆(ϕ, a).

a∈A

The global pseudo-regret after T decisions is RT := D.2

X

P

ϕ∈Φ RN (T ) (ϕ) (ϕ).

Decomposition of the Memory MDP

Lemma D.6 (Bandit decomposition of Mmem ). Under Assumption D.3, the expected cumulative pseudo-regret of any policy π on Mmem satisfies i X  XX h  E[RT (π)] = E RN (T ) (ϕ) (ϕ; π) = E Na(T ) (ϕ) ∆(ϕ, a). ϕ∈Φ a∈A

ϕ∈Φ

Proof. Write 1{·} for the indicator function, and let Ft−1 denote the σ-algebra generated by (ϕs , as , Gs )s<t . By Definition D.5, the random pseudo-regret after T decisions is RT (π) =

T T X X X X   µ(ϕt , a⋆ (ϕt )) − µ(ϕt , at ) = 1{ϕt = ϕ, at = a} ∆(ϕ, a), t=1

(9)

t=1 ϕ∈Φ a∈A

where we have rewritten µ(ϕt , a⋆ (ϕt )) − µ(ϕt , at ) by summing over the finitely many possible values of (ϕt , at ) (exactly one indicator is non-zero at each t). 20

Taking expectations on both sides of (9) and swapping sums by Fubini’s theorem (all quantities are non-negative and finite since |Φ|, |A| < ∞ and T < ∞):   T XX E[RT (π)] = E 1{ϕt = ϕ, at = a} ∆(ϕ, a) ϕ,a t=1

=

XX

∆(ϕ, a) E

XX

#

1{ϕt = ϕ, at = a}

t=1

ϕ∈Φ a∈A

=

" T X

h i ∆(ϕ, a) E Na(T ) (ϕ) ,

(10)

ϕ∈Φ a∈A (T )

where the last equality uses the definition Na (ϕ) =

PT

t=1

1{ϕt = ϕ, at = a}.

The first equality in the statement follows from regrouping the inner double sum by ϕ: for each fixed P (T ) ϕ, the contribution of that state to E[RT ] is a ∆(ϕ, a) E[Na (ϕ)] = E[RN (T ) (ϕ) (ϕ; π)], by the per-state identity in Definition D.5 together with Assumption D.3 (the per-state gaps ∆(ϕ, a) are deterministic functions of ϕ, not of the history). Lemma D.6 reduces the Memory MDP to |Φ| independent stochastic bandits and allows us to upper-bound RT state by state. D.3

Concentration of the Empirical Mean

Lemma D.7 (Hoeffding concentration, per-state). Fix (ϕ, a) ∈ Φ × A. Under Assumptions D.3–D.4, for any ε > 0 and any m ∈ N>0 ,   h i 2mε2 Pr |µ̂t (ϕ, a) − µ(ϕ, a)| ≥ ε Na(t) (ϕ) = m ≤ 2 exp − . (11) W2 (t)

Proof. Condition on the event {Na (ϕ) = m} and enumerate the m visit times τ1 < τ2 < · · · < τm ≤ t at which (ϕτi , aτi ) = (ϕ, a). Let Gi := Gτi ∼ Dϕ,a be the corresponding returns. By Assumption D.3, {Gi }m i=1 are i.i.d. with common mean µ(ϕ, a) and by Assumption D.4 each Gi ∈ [Gmin , Gmax ] with Gmax − Gmin = W . The empirical mean on this event is m 1 X µ̂t (ϕ, a) = Gi . m i=1 Step 1 (moment generating function bound). For every λ ∈ R and every i, Hoeffding’s lemma (see Lemma 2.2 in [40]) applied to the bounded variable Zi := Gi − µ(ϕ, a) ∈ [Gmin − µ, Gmax − µ] (an interval of width W ) gives
E[exp(λZi )] ≤ exp λ2 W 2 /8 . (12) The standard derivation of (12) proceeds by convexity: for Gi ∈ [Gmin , Gmax ] we may write Gi = θGmin + (1 − θ)Gmax with θ := (Gmax − Gi )/W ∈ [0, 1], so that eλZi ≤ θ eλ(Gmin −µ) + (1 − θ) eλ(Gmax −µ) . Taking expectations and optimizing the resulting exponent over the (log of the) centered mgf yields (12). Step 2 (Chernoff–upper tail). By independence of {Zi } and (12), "m # h i X (t) Zi ≥ mε Pr µ̂t (ϕ, a) − µ(ϕ, a) ≥ ε | Na (ϕ) = m = Pr i=1

P ≤ e−λmε E[exp(λ i Zi )] m Y   = e−λmε E eλZi

(Markov)

i=1

≤ exp −λmε + mλ2 W 2 /8 . 21

(13)

Minimizing the right-hand side of (13) over λ > 0 gives λ⋆ = 4ε/W 2 , so   h i 2mε2 (t) . Pr µ̂t (ϕ, a) − µ(ϕ, a) ≥ ε | Na (ϕ) = m ≤ exp − W2

(14)

Step 3 (two-sided bound). Applying (14) to {−Zi } in place of {Zi } (which is also i.i.d. with bounded support of width W ) yields the symmetric lower-tail bound   h i 2mε2 Pr µ(ϕ, a) − µ̂t (ϕ, a) ≥ ε | Na(t) (ϕ) = m ≤ exp − . W2 A union bound over the two tails gives (11). p √ Setting ε = c ln N (t) (ϕ)/m with c = W/ 2 in (11) gives the familiar UCB confidence radius:   q
−4 (t) . (15) Pr |µ̂t (ϕ, a) − µ(ϕ, a)| ≥ c ln Nm (ϕ) ≤ 2 N (t) (ϕ) D.4

Regret Bound for UCB-Based Selection

M EM C ON selects actions by maximizing the upper-confidence index r   √ ln N (t) (ϕt ) at ∈ arg max µ̂t (ϕt , a) + c , c = 1.4 ≈ W/ 2. (t) Na (ϕt ) a∈A | {z }

(16)

=: Ut (ϕt ,a)

Theorem D.8 (Per-state UCB1 regret). Under Assumptions D.3–D.4, running the UCB rule (16) at state ϕ for n pulls yields  X X   2 8W 2 ln n E Rn (ϕ) ≤ ∆(ϕ, a) . (17) + 1 + π3 ∆(ϕ, a) a∈A a:∆(ϕ,a)>0 | {z } | {z } constant term

logarithmic term

In particular, E[Rn (ϕ)] ∈ O |A| W 2 log n/∆min , i.e., logarithmic in n. Proof. Throughout the proof we drop the dependence on ϕ from the notation (we are analyzing a (t) single fixed state) and write Na (t) := Na (ϕ), N (t) := N (t) (ϕ), µ̂a (t) := µ̂t (ϕ, a), µa := µ(ϕ, a), ⋆ ⋆ ∆a := ∆(ϕ, a). Let a := a (ϕ). PThe goal is to upper-bound E[Na (n)] for each sub-optimal arm a; by Definition D.5, E[Rn (ϕ)] = a:∆a >0 ∆a E[Na (n)]. Step 1 (three-event decomposition). Fix a sub-optimal arm a with ∆a > 0 and a threshold   8W 2 ln n u := . ∆2a

(18)

We show that whenever Na (t) ≥ u and UCB1 nevertheless pulls arm a at time t + 1, at least one of the following three events holds: p E1 (t) : µ̂a⋆ (t) + c ln N (t)/Na⋆ (t) < µa⋆ , (19) p E2 (t) : µ̂a (t) > µa + c ln N (t)/Na (t), (20) p E3 (t) : µa⋆ < µa + 2c ln N (t)/Na (t). (21) Indeed, if UCB1 selects a over a⋆ at time t + 1 then Ut (ϕ, a) ≥ Ut (ϕ, a⋆ ), i.e., p p µ̂a (t) + c ln N (t)/Na (t) ≥ µ̂a⋆ (t) + c ln N (t)/Na⋆ (t). If none of E1 , E2 , E3 holds, then p µ̂a⋆ (t) + c ln N (t)/Na⋆ (t) ≥ µa⋆

(¬E1 )

≥ µa + 2c

p

ln N (t)/Na (t) p > µ̂a (t) + c ln N (t)/Na (t) 22

(¬E3 ) (¬E2 ),

contradicting UCB1’s selection of a. Step 2 (E3 is impossible when Na (t) ≥ u). If Na (t) ≥ u = ⌈8W 2 ln n/∆2a ⌉, then s r r ln N (t) ln n ∆2a ∆a W = ≤ 2c ≤ 2√ < ∆a = µa⋆ − µa , 2c 2 Na (t) u 8W 2 2 √ where we used N (t) ≤ n (so ln N (t) ≤ ln n) and the choice c = W/ 2. Hence E3 (t) cannot hold once arm a has been pulled u times. Step 3 (bounding Pr[E1 (t) ∪ E2 (t)]). We bound each of Pr[E1 (t)] and p Pr[E2 (t)] using Lemma D.7. For E2 (t), conditioning on Na (t) = s and applying (11) with ε = c ln N (t)/s gives     q 2 2 2s · c2 ln N (t)/s = N (t)−2c /W . Pr µ̂a (t) > µa + c ln Ns (t) Na (t) = s ≤ exp − 2 W √ With c = W/ 2, 2c2 /W 2 = 1, so the per-arm upper-tail bound is N (t)−1 . In the sharper version √ −4 below we use the √ standard UCB1 constant c = W 2 which yields N (t) ; since √ our code uses c = 1.4 ≈ W/ 2 ≈ 1.27 for W ≤ 1.8, we re-derive the theorem with c = W 2 for clarity and note that the constants in (17) remain valid up to a re-choice of the universal pre-factor. Marginalizing over s ∈ {1, . . . , N (t)}, N (t)

X

Pr[E2 (t)] ≤

N (t)−4 ≤ N (t)−3 ≤ t−3 .

(22)

s=1

The same argument applied to −Zi gives Pr[E1 (t)] ≤ t−3 . Step 4 (bounding E[Na (n)]). Let Ta := inf{t ≥ 1 : Na (t) ≥ u}; by Step 2,Ponce t ≥ Ta the arm a n can only be pulled if E1 (t) or E2 (t) holds. Therefore, writing Na (n) = u + t=u+1 1{at = a} and taking expectations, n X

E[Na (n)] ≤ u + ≤ u +

Pr[E1 (t) ∪ E2 (t)]

t=u+1 ∞ X

2 t−3

t=1

 ≤

2

8W ln n ∆2a

 + 2

∞ X

t−3

t=1

π2 8W 2 ln n +1+ , ≤ 2 ∆a 3 where we used

−3 ≤ t≥1 t

P

P

t≥1 t

−2

(23)

= π 2 /6, doubled by Step 3, giving π 2 /3.

Step 5 (aggregation). By Definition D.5, E[Rn (ϕ)] =

X a:∆a >0

=

X

∆a E[Na (n)] ≤

a:∆a >0

X 8W 2 ln n a:∆a >0

 ∆a

∆a

+



2

1 + π3

 8W 2 ln n  π2 + 1 + 3 ∆2a

 X

∆a .

a:∆a >0

Extending the right-most sum over all a ∈ A (the extra terms have ∆a = 0 and contribute nothing) yields (17). P Step 6 (asymptotic rate). Fix ∆min := mina:∆a >0 ∆a > 0. Then a:∆a >0 8W 2 ln n/∆a ≤ P |A| · 8W 2 ln n/∆min , and a ∆a ≤ |A| · W (the reward range bound). Hence E[Rn (ϕ)] = O(|A|W 2 ln n/∆min ). 23

Corollary D.9 (Global regret of M EM C ON). Let T be the total number of memory decisions. Summing Theorem D.8 over ϕ ∈ Φvisit and using Lemma D.6,       X X 8W 2 ln T X 2 |Φvisit | |A| W 2 log T  E[RT ] ≤ + 1 + π3 ∆(ϕ, a) ∈ O . ∆(ϕ, a) ∆min ϕ∈Φvisit

a∈A

a:∆(ϕ,a)>0

(24) Hence the average per-decision regret E[RT ]/T → 0 as T → ∞ at rate O(log T /T ). Remark D.10 (Empirical calibration). In our runs, |Φvisit | ≈ 300 and |A| = 9, giving a regret upper bound of order 103 · log T /∆min . For the observed success gaps (∆min ≳ 0.05) this matches the empirical observation that M EM C ON converges within ≲ 30 episodes per state. D.5

Convergence of the Reverse-Discounted Q-Update

The M EM C ON update rule on visited (ϕj , aj ) pairs after episode i is   Qt+1 (ϕj , aj ) = Qt (ϕj , aj ) + αt Gj − Qt (ϕj , aj ) , Gj := γ |ep|−j−1 · ri ,

(25)

where αt ∈ (0, 1) is the step size (constant αt ≡ α = 0.15 in our experiments). Definition D.11 (Bellman-style target). Define the target operator B : RΦ×A → RΦ×A by (BQ)(ϕ, a) := E[Gj | ϕj = ϕ, aj = a] = µ(ϕ, a). Lemma D.12 (Contraction-free fixed point). Under Assumption D.3, the operator B in Definition D.11 has the unique fixed point Q⋆ (ϕ, a) = µ(ϕ, a). Note B is not a contraction; however, because the target Gj does not depend on Q, convergence below is obtained from stochastic approximation rather than from contraction. Proof. B is a constant operator in Q: (BQ)(ϕ, a) = µ(ϕ, a) for every Q. Hence Q is a fixed point iff Q(ϕ, a) = µ(ϕ, a) for all (ϕ, a). Theorem D.13 (Almost-sure convergence of Qt ). Assume Assumptions D.3–D.4 and that ∞ X

∞ X

αt = ∞,

t=1

αt2 < ∞,

(26)

t=1

and that each (ϕ, a) is visited infinitely often (guaranteed by the UCB rule (16); see Lemma D.14 below). Then for every (ϕ, a) ∈ Φ × A, a.s.

Qt (ϕ, a) −−−→ µ(ϕ, a). t→∞

Proof. Fix (ϕ, a). Lemma D.14 gives that (ϕ, a) is visited infinitely often a.s.; let τk denote the k-th visit time and set βk := ατk ∈ (0, 1) (the step size used at the k-th update to Q(ϕ, a)). Condition (26) on the global αt implies the same on βk : ∞ X

∞ X

βk = ∞,

k=1

βk2 < ∞.

(27)

k=1

Let Yk := Qτk (ϕ, a) − µ(ϕ, a) and let Gτk ∼ Dϕ,a be the observed return at the k-th visit. Let Fk be the σ-algebra generated by all history through τk . Substituting (25) and using µ(ϕ, a) = (1 − βk )µ(ϕ, a) + βk µ(ϕ, a) gives the recursion Yk+1 = (1 − βk ) Yk + βk ξk+1 ,

ξk+1 := Gτk+1 − µ(ϕ, a).

(28)

2 By Assumption D.3, E[ξk+1 | Fk ] = 0, and by Assumption D.4, |ξk+1 | ≤ W so E[ξk+1 | Fk ] ≤ 2 2 W /4 (variance of a bounded variable of range W is maximized at W /4). Thus {ξk } is a bounded martingale-difference sequence.

We prove Yk → 0 a.s. in three steps via a supermartingale argument adapted from the classical stochastic-approximation proof of [16, Thm. 11.1]. 24

Step 1 (L2 bound). Squaring (28) and taking Fk -conditional expectations, 2 2 E[Yk+1 | Fk ] = (1 − βk )2 Yk2 + 2βk (1 − βk ) Yk E[ξk+1 | Fk ] + βk2 E[ξk+1 | Fk ]

≤ (1 − βk )2 Yk2 + βk2 W 2 /4 ≤ (1 − βk ) Yk2 + βk2 W 2 /4,

(29)

2

where we used (1 − βk ) ≤ 1 − βk for βk ∈ [0, 1], and E[ξk+1 | Fk ] = 0. Step 2 (Yk2 is a supermartingale up to a summable drift). Rearranging (29) gives 2 E[Yk+1 | Fk ] − Yk2 ≤ −βk Yk2 + βk2 W 2 /4.

Let Zk := Yk2 +

2 2 j≥k βj W /4 (well-defined by the second condition in (27)). Then

P

2 E[Zk+1 | Fk ] = E[Yk+1 | Fk ] +

X

βj2 W 2 /4 ≤ Yk2 +

j≥k+1

X

βj2 W 2 /4 − βk Yk2 = Zk − βk Yk2 ,

j≥k

so {Zk } is a non-negative supermartingale. Step 3 (a.s. convergence). By Doob’s supermartingale convergence theorem [16, Appendix A.5], Zk P converges a.s. to a finite limit Z∞ ≥ 0. Since j βj2 W 2 /4 → 0 as k → ∞, this forces Yk2 → Z∞ a.s. Moreover, summing the supermartingale inequality from k = 1 to K and taking expectations, E[ZK+1 ] +

K X

βk E[Yk2 ] ≤ E[Z1 ].

k=1

P∞ P Letting K → ∞ and noting E[Z1 ] < ∞ gives k=1 βk E[Yk2 ] < ∞. Combined with k βk = ∞ (first condition of (27)), this implies lim inf k→∞ E[Yk2 ] = 0. Since Yk2 → Z∞ a.s., dominated convergence (with the bound Yk2 ≤ W 2 from Assumption D.4) gives E[Yk2 ] → E[Z∞ ], forcing E[Z∞ ] = 0 and therefore Z∞ = 0 a.s. Hence Yk → 0 a.s., i.e., Qτk (ϕ, a) → µ(ϕ, a) a.s. Step 4 (extending to all times). Between consecutive visit times τk and τk+1 the sequence Qt (ϕ, a) is constant by (25) (only visited pairs are updated), so Qt (ϕ, a) → µ(ϕ, a) a.s. as t → ∞. (t)

Lemma D.14 (Infinite visits under UCB). Under the UCB rule (16), Pr[ Na (ϕ) → ∞ as t → ∞ ] = 1 for every (ϕ, a) ∈ Φvisit × A. (t)

Proof. Fix ϕ ∈ Φvisit ; we drop ϕ from the notation again and write Na (t) := Na (ϕ), N (t) := N (t) (ϕ). By definition of Φvisit , we have N (t) → ∞ a.s. as t → ∞. Step 1 (initialization). The UCB index Ut (ϕ, a) is conventionally set to +∞ whenever Na (t) = 0 (any arm never pulled has an infinite exploration bonus). Under this convention, the first |A| visits to ϕ necessarily pull each arm at least once, so Na (t) ≥ 1 for all (ϕ, a) after finitely many visits to ϕ; let t0 be the (random but a.s. finite) first time this holds. Step 2 (contradiction for the bounded case). Suppose, for a contradiction, that there exist a ∈ A and an integer M < ∞ with Pr[supt≥t0 Na (t) ≤ M ] > 0. On this event Na (t) is bounded by M for all t. Pick any other P arm a′ ∈ A \ {a}. At visit times t ≥ t0 to ϕ in which a′ is pulled, Na′ (t) → ∞ (since N (t) = b Nb (t) → ∞ and Na (t) ≤ M is bounded, so the remaining |A| − 1 arms collectively go to infinity; by pigeonhole at least one a′ satisfies Na′ (t) → ∞). Hence for that a′ and any constant C > 0 there exists a random t1 ≥ t0 with Na′ (t1 ) ≥ C. Step 3 (UCB bonus forces selection of a). At any visit t ≥ t0 to ϕ, Assumption D.4 gives µ̂t (ϕ, b) ∈ [Gmin , Gmax ] for every b, so the UCB indices are bounded as s r ln N (t) ln N (t) Ut (ϕ, a) = µ̂t (ϕ, a) + c ≥ Gmin + c , Na (t) M s s ln N (t) ln N (t) Ut (ϕ, a′ ) = µ̂t (ϕ, a′ ) + c ≤ Gmax + c . ′ Na (t) Na′ (t) On the event {supt Na (t) ≤ M }, at visit time t ≥ t1 we have Na′ (t) ≥ Na′ (t1 ) ≥ C. Then   p 1 1 Ut (ϕ, a) − Ut (ϕ, a′ ) ≥ (Gmin − Gmax ) + c ln N (t) √ − √ M C 25

  p 1 1 = −W + c ln N (t) √ − √ . M C √ √ √ Choose C =√4M so that 1/ M − 1/ C = 1/(2 M ) > 0. As t → ∞ the term p c ln N (t)/(2 M ) → ∞, so for all sufficiently large visit times t we have Ut (ϕ, a) > Ut (ϕ, a′ ), uniformly over every a′ ∈ A \ {a} that has been pulled at least 4M times. Since this is true for every such competitor a′ , UCB must select a at the next visit, incrementing Na (t) by 1—contradicting the assumption that Na (t) ≤ M for all t. Step 4. The above shows Pr[supt Na (t) ≤ M ] = 0 for every M < ∞. Taking a countable union over M ∈ N, Pr[supt Na (t) < ∞] = 0, i.e., Na (t) → ∞ a.s. As a was arbitrary, this holds for every (ϕ, a). Proposition D.15 (Mean-squared convergence rate). Under the hypotheses of Theorem D.13 with a constant step size αt ≡ α ∈ (0, 1), h
2 i αW2 E Qτk (ϕ, a) − µ(ϕ, a) ≤ (1 − α)2k Y02 + . (30) 2−α As k → ∞, E[Yk2 ] converges exponentially fast to the steady-state variance αW 2 /(2 − α) → 0 as α → 0+ . Proof. Squaring Yk+1 = (1 − α)Yk + αξk , taking expectations, and using E[Yk ξk ] = 0 (martingaledifference property) and E[ξk2 ] ≤ W 2 /4 gives 2 E[Yk+1 ] = (1 − α)2 E[Yk2 ] + α2 E[ξk2 ] ≤ (1 − α)2 E[Yk2 ] + α2 W 2 /4.

Iterating and summing the geometric series yields (30). Remark D.16 (Constant vs. vanishing p α). With our choice α = 0.15, Proposition D.15 predicts a steady-state standard deviation of α/(2 − α) · W ≈ 0.285 · 1.8 ≈ 0.51 around µ(ϕ, a). This is larger than the idealized vanishing-α regime but allows the policy to track slowly drifting reward distributions, which matches deployment conditions where the memory backend itself evolves over tasks. D.6

From Action Values to Policy Optimality

greedy Definition D.17 (Greedy and UCB policies). Given Q : Φ × A → R, let πQ (ϕ) := UCB arg maxa Q(ϕ, a) and πQ (ϕ; t) := arg maxa Ut (ϕ, a) with Ut as in (16). greedy Theorem D.18 (Asymptotic optimality of πQ ). Under the hypotheses of Theorem D.13, for every t ϕ ∈ Φvisit , greedy lim µ(ϕ, πQ (ϕ)) = µ(ϕ, a⋆ (ϕ)) a.s. t t→∞

Proof. By Theorem D.13, Qt (ϕ, a) → µ(ϕ, a) a.s. for all a ∈ A. Since A is finite and ∆min > 0, there exists a.s. a (random) time T0 (ω) < ∞ after which arg maxa Qt (ϕ, a) = a⋆ (ϕ); hence greedy πQ (ϕ) = a⋆ (ϕ) for all t ≥ T0 . t Corollary D.19 (Sample complexity to ε-optimality). For any ε ∈ (0, ∆min /2) and confidence δ ∈ (0, 1), the number of pulls nε at ϕ required so that |µ̂nε (ϕ, a) − µ(ϕ, a)| < ε uniformly over a ∈ A with probability ≥ 1 − δ satisfies  2  2|A| W nε ≤ log . (31) 2ε2 δ greedy For ε = ∆min /2, this suffices to guarantee πQ (ϕ) = a⋆ (ϕ).

Proof. Hoeffding (Lemma D.7) with m = nε gives per-arm failure probability ≤ 2 exp(−2nε ε2 /W 2 ); union-bound over |A| arms and solve for nε to match δ. 26

D.7

Warm-Start and the Finite-Sample Regime

Proposition D.20 (Warm-start as a Bayesian prior). Let Q0 (ϕ, a) be the warm-start prior from Table 6, interpreted as a Gaussian prior N (Q0 (ϕ, a), σ02 ) on µ(ϕ, a), and suppose observations Gi ∼ N (µ(ϕ, a), σ 2 ) (or, more generally, sub-Gaussian with parameter σ 2 ). The posterior mean after m ≥ 0 observations is σ0−2 Q0 (ϕ, a) + m σ −2 µ̂t (ϕ, a) , (32) σ0−2 + m σ −2
−1 with posterior variance Var[µ | µ̂t , m] = σ0−2 + mσ −2 . Replacing µ̂t (ϕ, a) by µ̃t (ϕ, a) and (t) 2 2 Na (ϕ) by the effective sample size meff := m + σ /σ0 in the UCB rule (16) yields the BayesianUCB regret bound  X X 8σ 2 ln n 2 σ2 E[Rn (ϕ)] ≤ (33) + 1 + π3 ∆(ϕ, a) − 2 ∆min , ∆(ϕ, a) σ0 µ̃t (ϕ, a) :=

a∈A

a:∆(ϕ,a)>0

so the asymptotic rate O(log n) is preserved and the additive constant is reduced by (σ 2 /σ02 ) ∆min . Proof. Step 1 (posterior computation). Given the prior µ(ϕ, a) ∼ N (Q0 (ϕ, a), σ02 ) and i.i.d. Gaussian observations Gi | µ ∼ N (µ, σ 2 ) for i = 1, . . . , m, the likelihood is ! m  m  1 X 2 p(G1 , . . . , Gm | µ) ∝ exp − 2 (Gi − µ) ∝ exp − 2 (µ − µ̂t )2 , 2σ i=1 2σ P 1 where µ̂t = m i Gi is the observed empirical mean. Multiplying by the Gaussian prior and completing the square gives a Gaussian posterior with mean and variance E[µ | G1:m ] =

σ0−2 Q0 + mσ −2 µ̂t , σ0−2 + mσ −2

Var[µ | G1:m ] =

σ0−2 + mσ −2

−1

,

(34)

which is (32). Equivalently, Var[µ | G1:m ] =

σ2 σ2 , = m + σ 2 /σ02 meff

meff := m + σ 2 /σ02 .

(35)

Thus meff plays the role of an “effective” sample size that is inflated by σ 2 /σ02 compared to m. Step 2 (Bayesian-UCB index). The Bayesian-UCB rule replaces µ̂ and Na in (16) with the posterior mean and effective sample size: s (t) et (ϕ, a) := µ̃t (ϕ, a) + c ln N (ϕ) . U meff For sub-Gaussian G, Lemma D.7 generalizes to a posterior-tail bound: conditional on meff ,   meff ε2 Pr[|µ̃t (ϕ, a) − µ(ϕ, a)| ≥ ε | meff ] ≤ 2 exp − , 2σ 2 which is the sub-Gaussian analogue of (11) with W 2 replaced by 4σ 2 and m by meff . Step 3 (regret decomposition, re-derived). Repeating the four-step argument of Theorem D.8 with meff in place of Na (t) and σ 2 in place of W 2 /4, the critical threshold (Step 1 of that proof) becomes   2 8σ ln n , ueff = ∆2a and the three-event decomposition yields (n)

E[meff (ϕ, a)] ≤

2 8σ 2 ln n + 1 + π3 , ∆2a

27

(36)

(n)

(n)

exactly as in (23) but with meff in place of Na (n). Rewriting meff (ϕ, a) = Na (ϕ) + σ 2 /σ02 and subtracting the prior mass from the left-hand side, E[Na(n) (ϕ)] ≤

8σ 2 ln n σ2 π2 + 1 + − . 3 ∆2a σ02

Step 4 (aggregation). Following Step 5 of the proof of Theorem D.8, E[Rn (ϕ)] P (n) a:∆a >0 ∆a E[Na (ϕ)] gives E[Rn (ϕ)] ≤

=

X X 8σ 2 ln n  2 σ2 X ∆a . + 1 + π3 ∆a − 2 ∆a σ0

a:∆a >0

a∈A

a:∆a >0

Bounding the final sum below by ∆min yields (33). The O(log n) rate is unchanged because only the constant term shrinks. In practice, the warm-start values encode the domain knowledge that R ETRIEVE and P LAN I NJECT usually help while N O O P usually hurts (see §C). By Proposition D.20 this shifts effective exploration toward untried or dis-favored arms in the early regime, which matches the ≲ 30-episode convergence observed empirically (Remark D.10).

E

Prompt Templates

This appendix lists every prompt string used by M EM C ON and its evaluation harness. We group prompts into: (C.1) benchmark solver system prompts shared across all memory baselines, (C.2) M EM C ON-specific prompts injected by the wrapper, and (C.3) baseline-specific memory-write/read prompts, for completeness. E.1

Benchmark Solver System Prompts

All memory methods (including M EM C ON) share the identical solver system prompt per benchmark, so that differences in reported performance isolate the memory component. ALFWorld solver. ALFWorld system prompt You are now in a household environment called Alfworld, and your tasks include locating objects, heating or cooling items, and other similar activities. NOTE: - You must strictly follow the syntactic structure of the steps (where ’a’ and ’b’ are variables): 1. take a from b. 2. go to a. 3. open a. 4. put a in/on b. (always write "in/on" together, never "in" or "on" alone.) 5. clean a with b. 6. heat a with b. 7. cool a with b. 8. use a. 9. think: xxx - You must check carefully whether your output command is consistent with the allowed commands above. Any output not among the listed commands is rejected.

ScienceWorld solver (excerpt).

28

ScienceWorld system prompt You are a helpful assistant to do scientific experiments in a text-based environment. In the environment, there are several rooms: kitchen, foundry, workshop, bathroom, outside, living room, bedroom, greenhouse, art studio, hallway. You should explore the environment and find the items you need to complete the experiment. You can teleport to any room in one step. For each turn, choose "Thought" or "Action". If "Thought", output "Thought: ... \n Action: ...". If "Action", output only "Action: ...". Only one Action per response. Available actions: open / close / activate / deactivate / connect / disconnect / use / look around / examine / look at / read / move / pick up / pour / mix / teleport to / focus on / wait / wait1. CRITICAL RULES: use EXACT object names as shown in observations; "focus on OBJ" is typically required at the end; read the task description literally.

PDDL solver (Blocksworld example). PDDL Blocksworld system prompt You are a robot with four actions: pickup, putdown, stack, and unstack. Blocks can be stacked on top of each other; the arm holds at most one block; the table holds the rest. Actions: - think: xxx (format: ‘think: ...‘) - pickup <block>: pick up a clear block from the table if the arm is empty. - putdown <block>: put the held block on the table. - stack <block> <block>: stack held top-block onto a clear bottom-block. - unstack <block> <block>: pick the top-block off a bottom-block when the arm is empty. You must strictly follow these actions; no other actions are allowed.

Analogous solver system prompts are used for barman, gripper, and tyreworld (see tasks/prompts/pddl prompt.py in the released code). TriviaQA / WebWalkerQA / GAIA. QA tasks follow benchmark-standard short-answer or multiple-choice prompts (“Answer: X” format for MCQA, a single concise string for open-answer). We do not modify the benchmark-provided prompts. E.2

MemCon-Specific Prompt Fragments

The M EM C ON wrapper never adds a second LLM call, so it injects only two types of strings into the retrieved context. Generalized plan injection. Injected by P LAN I NJECT / R ETRIEVE [Proven plan for ’{goal type}’ tasks] 1. {step 1 generalized} 2. {step 2 generalized} ... k. {step k generalized} Adapt object/location names to your current task.

29

Here each step is produced by generalizing a successful trajectory: numbered location and object instances are replaced with categorical placeholders (e.g., "go to shelf 3" → "go to [shelf]", "take mug 1 from diningtable 2" → "take [mug] from [diningtable]"). The regularexpression rewriter covers the standard ALFWorld/ScienceWorld vocabulary (shelves, cabinets, drawers, containers, common foods, tools, etc.). Goal decomposition (multi-object tasks).

Injected for ALFWorld puttwo and analogous composite goals [TWO-OBJECT TASK: Complete all steps for object 1 first, then repeat for object 2] 1. Find & take first object → put it at target. 2. Find & take second object → put it at target. [Reference: single-put plan] 1. {step 1} 2. {step 2} ...

The second block reuses the generalized plan for the simpler single-object variant (put) when one has been learned, providing an additional hint to the LLM agent. E.3

Baseline Memory-Module Prompts

For full reproducibility we summarize the memory-write/re-rank prompts used by the baselines we re-implemented on top of the shared two-method memory interface. Full text of these prompts is in the released code. Voyager / MemoryBank trajectory summarizer.

Trajectory-summarization system prompt You are a helpful assistant that writes a description of the task resolution trajectory. 1) Try to summarize the trajectory in no more than 6 sentences. 2) Your response should be a single line of text.

Generative / ExperienceBank relevance scorer.

Relevance-scoring system/user prompts System:

You are an agent designed to score the relevance between two pieces of text.

User: You will be given a successful case and an ongoing task. Do not summarize either case; evaluate how relevant and helpful the successful case is for the ongoing task, on a scale of 1--10. Success Case: {trajectory} Ongoing task: {query} Score:

ChatDev phase-based summarizer.

30

Phase-based summarization system prompt You are an agent skilled in summarization. Your task is to generate phase-based summaries from given execution records of an agent’s task. These summaries help the agent efficiently utilize existing information, avoid redundant computations, and ensure task continuity. 1. Phase-based summarization: organize records into logical phases and extract key steps. 2. Task relevance: explain what has been completed and what remains. 3. Clarity and conciseness: precise language, no unnecessary details. If intermediate states are incorrect or irrelevant, filter or correct them to make the summary more accurate.

OAgents rule induction. Rule-comparison system prompt for OAgents You are an advanced reasoning agent that derives general rules from examples. will receive one successful trial and one failed trial. Goal: compare the positive and negative examples to extract insights. must be concise and expressed as high-level reasoning principles.

You

The insights

Output format: each line is one of AGREE <EXISTING RULE NUMBER>: <EXISTING RULE> REMOVE <EXISTING RULE NUMBER>: <EXISTING RULE> EDIT <EXISTING RULE NUMBER>: <NEW MODIFIED RULE> ADD: <NEW RULE>

G-Memory / LatentMem. Both use a two-stage pipeline: a LatentMem-specific insight extraction prompt (distinct per method but structurally similar to the OAgents rule-induction prompt) plus Chroma-vector retrieval over raw trajectory embeddings. The exact strings are long and exist verbatim in the referenced upstream repositories; we do not reproduce them here but note that they are identical to the ones used in Zhang et al. [9] and Ou et al. [10] respectively.

31