WorksComputer Science
Learning Personalized Memory Gating from Delayed One-Sided Feedback
Abstract
Long-term memory enables language-model agents to personalize future interactions, but a finite memory bank cannot preserve every extracted fact. Existing memory gating policies are typically shared across users and therefore fail to account for user-specific patterns of future reuse. In this paper, we study memory gating at the fact level. We first propose a retrieval-based labeling strategy that labels each fact by whether it is later retrieved and incorporated into responses. We then formulate online memory gating as contextual apple tasting with delayed one-sided feedback, and propose Warm-Start UCB, which combines offline learning from existing data with online adaptation to the current user. Our theoretical analysis establishes a high-probability regret upper bound of when the delay window is at most , where is the total number of rounds, is the initialization error, is the dimension of the feature map, and hides constant and poly-logarithmic factors. The results of our experiment demonstrate that our method outperforms all baselines under different memory budgets and history lengths, establishing it as a promising personalized memory gating policy.
Introduction
Memory systems, which extract and store important information during human-AI interaction, have been widely deployed in large language model (LLM)-based agents ([28, 52, 14]). Typically, a memory system extracts candidate facts from each dialogue, stores a subset in a memory bank, and retrieves relevant entries for later queries. Because storage and context budgets are finite, the system must decide which facts are sufficiently valuable to preserve.
Existing systems generally make this decision using criteria shared across users, such as heuristics like whether a fact expresses a stable preference, profile attribute, or ongoing goal ([29, 52]), or using policies learned from long-context training data ([47, 36] (Yu et al. 2026)). Nevertheless, such universal criteria overlook the heterogeneity across different users. In et al. [23] formalized this issue at the session level and introduced PerMem-Bench, together with several LLM-based storage-gating baselines. Their results show substantial headroom between perfect personalized gating and existing causal baselines, motivating methods that learn directly from user-specific interaction outcomes.
To learn directly from user-specific interaction outcomes, we first need to identify a feedback signal grounded in the interaction that reflects the utility of each fact. While a deployed system does not observe whether a discarded fact would have been useful, for a stored fact, later retrieval provides a natural signal of future utility: a fact is utilized if it is hit by the retrieval and incorporated into the response in some later conversation. This implies that whether a fact gets retrieved and confirmed by the LLM agent can serve as a flag of utility, and therefore provides natural and reliable guidance for learning a memory gating policy.
The retrieval-based feedback has two outstanding features: the feedback is only available on those added facts, and it becomes meaningful only after some unknown delay. To capture this nature, we formally frame the personalized memory gating problem as an apple tasting with one-sided delayed feedback problem ([18, 42]). We further propose a two-stage learning strategy, Warm-Start UCB. The first stage learns the utility pattern from data of existing users. The second stage adapts to user-specific patterns during online interaction via an upper confidence bound (UCB) algorithm. Our theoretical analysis and empirical results verify the effectiveness of Warm-Start UCB as a gating policy. Our contributions are summarized as follows:
We propose a labeling pipeline for learning personalized memory gating, which derives utility labels from downstream retrieval outcomes, refined through LLM-judge verification. This labeling strategy provides a direct feedback for memory gating learning, without relying on heuristic or downstream reward signals.
We frame personalized memory gating as an apple tasting with one-sided delayed feedback problem. To solve this problem, we propose a two-stage learning strategy, Warm-Start UCB. Our theoretical analysis implies that Warm-Start UCB effectively leverages the offline data while evolving towards user-specific patterns through online interaction.
We empirically evaluate Warm-Start UCB on our benchmark across a range of memory budgets and interaction lengths. Experiment results show that Warm-Start UCB consistently outperforms previous LLM-based methods and the naive admit-all baseline, suggesting that Warm-Start UCB serves as an effective gating policy for personalized memory.
Notation. We use to denote the set . In this work, we use lowercase letters to represent scalars, and denote vectors and matrices by lower and uppercase boldface letters respectively. Given a vector , we denote the vector’s -norm by . We further define given a positive semidefinite matrix . For two semidefinite matrices , we use if for any . We reserve for the identity matrix. For nonnegative sequences and , we write interchangeably with if , or if , and , or alternatively, , if and . We further employ , , and to hide polylog factors. We use to denote the indicator function. For any , we denote and .
Related Work
Personalized Memory System. Memory systems are widely used in various applications, including embodied systems ([55, 44]), personal assistants ([45, 51]) and recommender systems ([43]), incentivizing a long line of work in improving the effectiveness and efficiency. One direction mainly focuses on learning a policy that selectively extracts and persists crucial information from the interaction history ([14, 54, 47, 37]). Another direction focuses on leveraging various data structures to capture relation between memory units to improve subsequent retrieval ([46, 48, 22, 32, 26]). Despite these advances, most existing systems employ a universal storage policy and therefore fail to fully account for the heterogeneity across different users. In et al. [23] first formalize this limitation and introduce PerMem-Bench for evaluating personalized memory systems. They further propose several baseline approaches that operate the gating at session level, with LLM-based learning-free methods as the backbone. Compared to In et al. [23], we consider fact-level online adaptation from retrieval-derived feedback, which eliminates the reliance on human or LLM-based heuristic. This results in an apple tasting with one-sided delayed feedback formulation.
Learning with Apple Tasting Feedback. Apple tasting, introduced by Helmbold et al. [18, 19] is one of the canonical models for one-sided feedback, where the binary outcome is only revealed under the positive action. Apple tasting has been studied under several distinct comparators and modeling assumptions. In online binary classification against a hypothesis class, Raman et al. [31] characterize agnostic learnability through Littlestone dimension and establish a realizable-case trichotomy; Chase & Mehalel [13] study the additional restriction to deterministic learners. Apple tasting also appears as a canonical partial-monitoring or feedback-graph problem when regret is measured against a fixed action ([5, 2, 12]), with rates depending on the precise loss, feedback, and adversary model. Contextual variants have been studied through partial monitoring with side information, Bayesian logistic models, feedback-graph reductions, and log-loss ([4, 15, 50, 3]). Extension has also been made to other settings like fairness-aware ([7, 6]) and strategically manipulated context ([17]).
Learning with Delayed Feedback. There are long lines of work studying decision making problem with non-immediate feedback, the most canonical among which is that the delay is generated stochastically or adversarially independently of the feedback. In this setting, a regret comparable to the non-delay counterpart up to only additive terms of the delay is provably achievable under both multi-armed setting [24, 11, 39, 8, 56, 16, 27, 34] and linear setting [53, 20, 40, 9, 35]. Another line of work considers delayed feedback that is entangled with the feedback structure [25, 38, 33], among which the most relevant to us are Vernade et al. [41, 42] that studied the running-zero-flipping-one delay model and achieved regret upper bound [42], where is the dimension of feature map and is a high-probability upper bound of the stochastic delay. In this paper, we adopt the running-zero-flipping-one delay model with apple-tasting feedback to account for the specific structure in agentic memory system, where feedback is only available at added memory entries.
Dataset Construction
In this section, we introduce a retrieval-based labeling pipeline for learning memory gating policy, and provide a quick analysis for how the utility patterns are shared across users and how they differ. We defer the meta-evaluation of label validity to Appendix § 7.§ 2 and statistics of the constructed benchmark to Appendix § 7.§ 3.
Benchmark Construction
Our construction begins with any corpus of user-LLM interaction history between user and the LLM, denoted by , such that each session is composed of , where is the user’s -th prompt and the agent’s corresponding response in the -th session of the entire interaction history between user and the agent. In this paper, we consider the corpus generated via the strategy in In et al. [23]. Specifically, we adopt the pre-generated PerMem-Bench-S (PerMemBench-S), and additionally synthesize a longer dataset (PerMemBench-L), to better capture the long-horizon nature of human-AI interaction.
Fact Extraction. For each user , we process the sequence of session, in chronological order by feeding them into an off-the-shelf memory system.1 Starting from an empty memory bank , for each session , the memory system extracts a collection of candidate atomic facts and then merges these candidate facts into the memory bank . In plain words, is the memory bank before the -th session, if we add all extracted facts and the memory bank has infinite budget.
Retrieval-Based Labeling. After constructing the pool of candidate facts , we now assign each candidate fact a binary utility label indicating its usefulness. Recall that a fact can only be useful if it gets retrieved at some later point. Formally, fix a fact , for every user turn with , an LLM first decides whether answering that turn requires querying memory at all. For turns judged to require memory, the same LLM formulates a natural-language query and invokes the retriever of the memory system with query against the memory bank state . is labeled with “required for $x_{t',i'}” only if appears among the top- retrieval hits.
LLM-Judge Verification. A retrieval hit alone is a noisy relevance signal: a fact may be topically related to without actually being needed to answer it (e.g., a temporal mismatch). We therefore filter the obtained retrieval hits with an LLM judge. For each pair of such that hit by the retriever for , we ask an LLM to judge whether the presence of in the context is necessary for the answer to , or substantially improves the answer quality. We denote all facts verified by this procedure with
as all valid retrieval hits. Finally, to mitigate potential neglect of the retrieval system, for all where the retrieval results in no strong match (i.e., the scores of all retrieved facts lie below a threshold), we employ an LLM to inspect whether there is a subset of facts from the top retrievals that collectively help with answering the user’s prompt. We denote these prompt-fact pairs as and merge them with to obtain the final set of valid retrieval hits . The final utility label is given by .
Evaluation Protocol. During evaluation, we consider a memory budget with a fixed budget size . For each distinct fact , the gating decides whether it should be added to the memory bank. If the decision is “add” and the bank is full, then the earliest entry in the bank will be evicted. Our main metric is retrieval-hit retention rate (RHR), which is the proportion of valid hits in that are realized under the fixed budget. In particular,
At a high level, the RHR captures how well a policy preserves facts until the turn where they actually make a difference, given that the memory budget is limited. A miss of fact at stems from one of two reasons: the gating policy drops , or it adds too many non-required facts so that gets evicted too early. Hence, a policy that attains a high RHR usually adds the required facts to the memory bank and drops unnecessary ones. Besides this, we also consider the F1 score of a gating policy, by treating the storage decision itself as a binary classification problem against the ground truth labels.
Meta Analysis
In this section, we provide a preliminary study of the heterogeneity and homogeneity among different users. To do this, for each fact, we predict the binary utility label using the TF-IDF representation of the fact content and a logistic regression classifier. We compare two evaluation regimes per user: (i) Self, a stratified -fold cross-validation using only ’s own facts, and (ii) leave-one-user-out (LOUO), a single shared-vocabulary model trained on the pooled facts of the other 19 users and evaluated on .
The results are summarized in Table 1. First, we observe that the LOUO model itself is far above random (AUC 0.622 and 0.665, respectively, vs. 0.5), meaning that a classifier that has never seen the held-out user’s facts still recovers a considerable share of the signal: part of what makes a fact useful for future interactions is shared among users. Despite this, the self AUC exceeds the LOUO AUC prominently, indicating that a substantial, user-specific component of the gating rule does not transfer under a single fixed global classifier. This coexistence of homogeneity and heterogeneity indicates that, to make the best use of the data, a policy should both learn from other users and adapt to the current one. This motivates the proposed methods, introduced in the next section.
| Dataset | Self AUC | LOUO AUC | Gap |
| PerMemBench-S | |||
| PerMemBench-L |
Table 1. Self (within-user CV) vs. LOUO (fixed global model) TF-IDF + logistic regression AUC for the fact-gating label, averaged over 20 users.
Algorithm and Analysis
In this section, we introduce an online learning model that captures the structure of retrieval-based feedback, along with an algorithm for learning a memory-gating policy from this feedback.
Problem Setup
We model the personalized memory gating problem as a contextual bandit with apple-tasting, delayed, one-sided feedback problem and describe the formal setup in this section. For simplicity, we fix a single user and omit the user subscript.
Interaction Protocol
At each round , the learner observes a context and chooses an action . Here, the context is a feature representation2 of the candidate memory fact extracted at timestamp , and the action is the memory system’s gating decision: add commits the fact to the memory bank, while skip discards it. The learner receives different feedback depending on the action taken. If , the learner discards the fact and observes nothing at any future time. If , the environment simultaneously samples a delay from a fixed distribution , independently, and at each subsequent time , the learner observes the censored conversion indicator
where is the actual label such that indicates that the fact is utilized by some future user turn, and indicates that the fact is never used. Moreover, is the number of rounds until the utilization is confirmed (e.g., the fact is retrieved for a later turn). The observation begins at and, if and only if , flips to 1 once the delay elapses. A persistent 0 is ambiguous between a transient fact and a required fact whose confirming retrieval has not yet occurred.
Remark 4.1. This one-sided feedback structure, where the outcome of a decision is only ever revealed when the learner chooses the positive action, is classically termed apple tasting3. Decision-making problems with such a feedback structure have been widely studied in the previous literature [18, 19]. Our problem can be seen as a combination of the apple-tasting feedback and the delayed running-zero-flipping-one feedback considered in Vernade et al. [42].
We assume the learner has some knowledge of the delay distribution.
Assumption 4.2. There exist some known and such that , for any .
Furthermore, we assume , where is a user-specific function and is the utility score. A larger means a higher probability that the information in is used in the future. We assume that there exists some unknown , such that , where the features admit the following regularity conditions.
Assumption 4.3. There exists some known constant such that for all .
Learning Objective
With store-gain and asymmetric error costs , the reward is
Without loss of generality, we assume . Taking expectations over , the action add is preferred if and only if , where , so the oracle is the threshold policy . The learner’s goal is to minimize the pseudo-regret against ,
Remark 4.4. While the interaction protocol captures two key features of feedback from retrieval-based labeling, apple-tasting and one-sided delay, we notice that our online learning model still differs from practice in several ways. For example, within all retrieved and verified facts, their utility still varies: some are rarely retrieved and incorporated, whereas others are used more frequently. Also, the cost for adding a non-required fact may vary over time: it will be higher when the memory bank is nearly full and lower when it has more capacity. Extending the model to account for these variations, and developing algorithms for the resulting settings, are promising directions for future work.
Algorithm 1 Warm-Started Ridge UCB with One-Sided Delayed Feedback (Warm-Start UCB)
Require: Threshold , warm-start center , prior shape , regularization parameter , confidence level , delay parameters , horizon
Initialize , , , .
for do
Observe context
Compute
Play if . Otherwise play
Observe all delayed feedback available at the end of round
Set , , and
Set
end for
Training from Other Profiles
The meta-analysis in § 3.2 suggests that users’ storage-preference parameters contain both a shared component and a user-specific component. This motivates using data from other users to construct an informative warm start for the current user. We formalize the quality of this warm start through the following high-probability assumption.
Assumption 4.5. The learner is given a prior center , a positive-definite matrix , and a known radius such that
Here, the probability is taken over both the current user’s parameter and the randomness in the pretraining data used to construct and .
Overall, Assumption 4.5 states that the learner, through techniques like linear regression on other existing users, has access to a sufficiently accurate estimate of the center of the prior distribution of the per-user ground truth , which is close to any realized with high probability. In fact, Assumption 4.5 is plausible given the meta-analysis in § 3.2 and standard analyses of random-design linear regression (Hsu et al. [21]). In particular, let denote a population-level parameter shared across users. The transferability observed in § 3.2 suggests that the current user’s parameter is concentrated around this common component. Therefore, it is reasonable to make the assumption that, with probability at least ,
At the same time, the cross-user predictability demonstrated in § 3.2 suggests that data from other users can be used to estimate the shared component. Standard random-design linear-regression results, such as Hsu et al. [21], can be used to establish that, with probability at least ,
Combining (1) and (2) with the triangle inequality gives with probability at least . Thus, Assumption 4.5 holds with and . We refer to Appendix D for a detailed discussion.
Online Adaptation
While a parameter pre-trained on other profiles might already serve as a good proxy for most individual profiles, it does not account for the heterogeneity revealed in § 3.2, and therefore leads to linear regret as the time horizon . To address this issue, we introduce an online adaptation strategy that starts from the pre-trained parameter but still adjusts towards the user’s specific parameter during the online interaction. The strategy is summarized in Algorithm 1. Similar warm-start strategies have also been applied in previous bandit papers such as Cella et al. [10]; Peleg et al. [30].
Algorithm 1 extends previous algorithms for one-sided delayed feedback Vernade et al. [42] to the apple-tasting feedback setting. At each round, Algorithm 1 observes the context and computes an index that is optimistic for with high probability, inspired by previous work on linear contextual bandits Abbasi-Yadkori et al. [1]. Then the algorithm plays add if and only if the index exceeds the threshold . Finally, the algorithm updates its parameter estimate based on the most recently available feedback.
The key challenge arises from the estimation of the parameter. For every added sample and current time step , a running-zero label is ambiguous: it might be either that the fact is not useful (i.e., ) or that it is still under the delay (i.e., ). To address this issue, we follow the approach in Vernade et al. [42] and truncate the observation by a window of length : for each added sample , we wait for rounds and treat its label as 1 if we observe a flip, and 0 otherwise, even if it flips to 1 later. Formally, define the truncated observation
Our next step is to treat the truncated observation as the regression label. Notice that
Consequently, the regression on the feature-label pairs targets . Since our regression target is rather than , we compensate for the scaling by multiplying our estimate by when comparing it to the threshold . Based on the regression, we compute the confidence radius of the estimate
where , and is a sub-Gaussian parameter of the noise, which can be taken to be in our setting. Finally, because observations from the most recent added samples may not yet have reached their final truncated values, the confidence radius contains an additional term corresponding to the pending-observation rounds
Remark 4.6. Unlike the original algorithm of Vernade et al. [42], our decision rule compares the estimated utility against a fixed, exogenous threshold . In contrast, comparisons among contemporaneous arms are invariant to a common multiplicative factor. Consequently, our algorithm must know , or have a sufficiently accurate estimate of it, in order to rescale the decision threshold.
Theorem 4.7. Suppose Assumptions 4.2, 4.3 and 4.5 hold. Fix any . Then, with a proper choice of that depends on , , , , , for sufficiently small , with probability at least , Algorithm 1 satisfies
where hides all logarithmic factors and the dependency on .
Theorem 4.7 shows that, when the pre-trained estimate is accurate enough, the per-step regret is roughly bounded by , so the algorithm only incurs regret when is small. On the other hand, when is large, the algorithm enjoys a sublinear regret, indicating that the proposed strategy effectively learns the user-specific parameter.
Experiments
Table 3: Results on the PerMemBench-L benchmark. We use bold for the highest score and underline for the second highest. For LLM-based methods, “(Ours)” indicates the corresponding method with our fine-grained prompt. The results show that Warm-Start UCB significantly outperforms the Universal baseline and LLM-based methods uniformly across all budget sizes.
| Metric | Micro Average | Macro Average | ||||||||
| Budget Size | 120 | 250 | 500 | 800 | 1000 | 120 | 250 | 500 | 800 | 1000 |
| Oracle | 54.30 | 78.61 | 97.51 | 100.00 | 100.00 | 58.68 | 82.62 | 98.33 | 100.00 | 100.00 |
| Universal | 20.17 | 35.28 | 50.77 | 65.73 | 73.77 | 22.03 | 37.13 | 52.55 | 67.50 | 75.71 |
| Greedy | 19.65 | 29.19 | 40.59 | 47.42 | 49.19 | 20.38 | 30.02 | 40.53 | 46.50 | 47.68 |
| Greedy (Ours) | 18.64 | 29.87 | 45.55 | 58.12 | 62.87 | 19.54 | 31.32 | 46.59 | 58.56 | 63.10 |
| Context | 17.01 | 25.43 | 36.30 | 41.56 | 43.49 | 17.70 | 25.93 | 36.50 | 40.61 | 42.52 |
| Context (Ours) | 18.76 | 28.87 | 45.13 | 57.33 | 63.49 | 19.79 | 30.13 | 46.76 | 58.54 | 64.40 |
| Cold-Start UCB | 20.75 | 35.46 | 51.22 | 66.82 | 74.42 | 22.12 | 37.33 | 53.09 | 68.67 | 76.43 |
| Pre-trained Scorer | 24.72 | 38.08 | 55.21 | 66.13 | 75.02 | 26.44 | 39.98 | 56.88 | 67.02 | 76.05 |
| Warm-Start UCB | 25.22 | 37.77 | 56.14 | 69.21 | 76.46 | 26.73 | 39.87 | 57.92 | 69.93 | 77.52 |
Table 3. Results on the PerMemBench-L benchmark. We use bold for the highest score and underline for the second highest. For LLM-based methods, “(Ours)” indicates the corresponding method with our fine-grained prompt. The results show that Warm-Start UCB significantly outperforms the Universal baseline and LLM-based methods uniformly across all budget sizes.
Baselines and Methods
Model-Free Baselines. We follow In et al. [23] and consider the following two baselines that do not operate on a specific model
Oracle: The memory system is provided with the ground truth labels and only adds the required facts, serving as the skyline of the performances.
Universal: The memory system adds every extracted fact into the memory bank, representing current memory systems.
LLM-Based Methods. We also consider the causal LLM-based baselines introduced in In et al. [23]. For both LLM-based baselines, we use gpt-5-mini as the backbone and evaluate two prompting strategies. One follows the prompt of In et al. [23], while the other, denoted by “Ours”, uses a more fine-grained rubric that additionally accounts for the remaining capacity of the memory bank. The complete prompts are provided in Appendix § 8.§ 1.
LLM-Greedy. For each extracted fact, an LLM predicts whether the fact captures crucial information that is likely to be useful in a future session. The prediction is based only on the current fact, without access to the user’s previous interaction history.
LLM-Context-Aware. After each session, the dialogue is summarized in one or two sentences. For each subsequent fact, the LLM is provided with the current fact, the current session, and a sliding window containing the most recent session summaries, and is asked to determine whether the fact, given the context, might be required in the future.
Linear Gating Methods. We consider three linear gating methods, all of which use the same linear feature representation of the facts. Besides the Warm-Start UCB introduced in Algorithm 1, we consider its two variants as its ablations. We refer to Appendix § 8.§ 2 for the implementation details.
Cold-Start UCB. Algorithm 1 run with and no access to other users’ data. The gating rule is learned using only the current user’s feedback, which isolates the contribution of online adaptation.
Pre-trained Scorer. A linear scorer fitted offline on the labeled facts of other users and kept frozen throughout the interaction, without adaptation to the current user’s feedback, which isolates the contribution of cross-user pre-training.
Experiment Results
The results are summarized in Table 2 and Table 3. We report the RHR as a percentage under both micro and macro averaging. Micro averaging pools valid retrieval hits across users, whereas macro averaging first computes the RHR separately for each user and then averages across users.
| Metric | Micro Average | Macro Average | |||||||
| Budget | 60 | 120 | 250 | 500 | 60 | 120 | 250 | 500 | |
| Oracle | 69.34 | 92.99 | 100.00 | 100.00 | 77.28 | 95.22 | 100.00 | 100.00 | |
| Universal | 17.44 | 35.94 | 56.93 | 80.60 | 19.34 | 39.29 | 60.76 | 84.91 | |
| Greedy | 23.01 | 32.95 | 44.49 | 47.34 | 24.86 | 34.16 | 45.08 | 47.56 | |
| Greedy (Ours) | 23.94 | 35.99 | 53.70 | 68.13 | 26.11 | 38.29 | 55.00 | 67.87 | |
| Context | 23.39 | 32.28 | 42.96 | 45.28 | 25.33 | 33.20 | 42.95 | 45.21 | |
| Context (Ours) | 23.34 | 36.37 | 52.11 | 66.32 | 24.72 | 37.75 | 53.09 | 66.29 | |
| Cold-Start UCB | 20.55 | 37.63 | 56.62 | 82.13 | 23.29 | 41.49 | 60.95 | 83.93 | |
| Pre-trained Scorer | 24.35 | 38.62 | 56.90 | 79.64 | 26.52 | 41.72 | 59.73 | 81.06 | |
| Warm-Start UCB | 24.10 | 38.64 | 58.73 | 84.48 | 26.40 | 41.98 | 61.84 | 86.94 |
Table 2. Results on the PerMemBench-S benchmark. We use bold for the highest score and underline for the second highest. For LLM-based methods, “(Ours)” indicates the corresponding method with our fine-grained prompt. The results show that Warm-Start UCB outperforms the Universal baseline and LLM-based methods uniformly across all budget sizes.
Results on PerMemBench-S. As shown in Table 2, Warm-Start UCB consistently outperforms the Universal baseline and all LLM-based gating methods across every memory budget under both micro and macro averaging. For example, at , our method performs on par with the best LLM-based methods and improves over the Universal baseline by 6.66 micro and 7.06 macro percentage points. On the other hand, when the memory budget is large, LLM-based methods underperform the Universal baseline, while our method still improves over it by 1.80 micro and 1.08 macro points at , and by 3.88 micro and 2.03 macro points at $B = 500. To summarize, the results indicate that our method consistently outperforms the considered baselines.
Meanwhile, the comparison among the three linear methods further reveals the complementary roles of pre-training and online adaptation. Under the smallest budget, the feedback signal is sparse, so the improvement mostly comes from Pre-trained Scorer. On the other hand, with a larger budget, more online feedback becomes available, which improves the performance of UCB. Since our proposed method combines the two strategies, it yields a stable improvement across all budget sizes.
Results on PerMemBench-L. Table 3 shows a consistent pattern on the substantially longer interaction trajectories of PerMemBench-L. Our method, Warm-Start UCB, achieves the best non-oracle result in eight of the ten evaluation columns and the second-best result in the remaining two, where it is narrowly below Pre-trained Scorer at . Compared with the Universal baseline, our method improves the micro RHR by 2.49–5.37 percentage points and the macro RHR by 1.81–5.37 points across the five evaluated budgets.
Moreover, a longer interaction history means that both pre-training and online adaptation are exposed to more data and feedback. Nevertheless, the results show that, compared to the Universal baseline, Pre-trained Scorer leads to a considerable improvement, while UCB without initialization performs only marginally above the Universal baseline. Despite this, we still observe a consistent improvement brought by online adaptation when the memory budget is large. This result indicates that a population-level gating rule transfers useful information to a new user, but cannot fully capture the user’s individual storage preferences. Updating the rule with user-specific feedback is therefore essential for maintaining performance over long interaction horizons.
Remark 5.1. Across all experimental settings, we see that LLM-based methods are comparable to the Universal baseline under small budgets. However, they become inferior to the Universal baseline under larger budgets, and the gap increases with the memory budget size. This observation is consistent with the results in In et al. [23]. We also observe that a more fine-grained, capacity-aware prompt only mitigates this inferiority but hardly resolves it.
Ablation Studies
Learning Dynamics. To examine whether the online methods genuinely adapt to the current user, we partition each user’s interaction trajectory into ten session-position deciles and report the F1-score improvement over the Universal baseline within each decile. Figure 1 presents the results on PerMemBench-L for representative memory budgets; the remaining budgets and the corresponding PerMemBench-S results are provided in Appendix § 9.

Figure 1. Learning dynamics on PerMemBench-L: F1 gain over the Universal baseline in each session-position decile under memory budgets . Shaded regions denote the 95% CI over all users. The gating quality improves in later deciles for online methods Cold-Start UCB and Warm-Start UCB.
As suggested by the plots, Cold-Start UCB begins with little or even negative improvement over the Universal baseline because it has not yet received enough one-sided, delayed feedback to learn the current user’s gating rule. Its performance gradually improves in later deciles, confirming that the online updates extract useful information from the user’s interaction history. In contrast, Pre-trained Scorer provides an immediate positive uplift but exhibits comparatively limited improvement as the interaction proceeds because its parameter remains fixed. Warm-Start UCB combines the strengths of both methods. It begins with the transferable knowledge supplied by pre-training and then increasingly separates from the frozen policy after user-specific feedback becomes available, also verifying the conceptual superiority of Warm-Start UCB.
Effect of the Pre-training Pool Size. We next vary the number of user profiles included in the pre-training pool while keeping the held-out test user fixed. Figure 2 reports the best micro and macro RHRs on PerMemBench-L for pre-training pool sizes in . Performance improves monotonically with the number of pre-training profiles under every displayed budget and both averaging schemes. Notably, the curves continue to improve at a pool size of 15, especially for and , suggesting that the pre-trained scorer has not yet saturated and may benefit from a larger and more diverse collection of user profiles.
Figure 2. Effect of the pre-training pool size on PerMemBench-L: best micro- and macro-averaged RHRs under . The results show that the performance continues to improve as the pretraining pool size grows.
Conclusion and Future Work
In this paper, we study the personalized memory gating problem. We first provide a retrieval-based utility labeling pipeline, based on which we construct a dataset for memory-gating evaluation. We further frame the problem as an apple tasting with one-sided delayed feedback problem, and propose an algorithm for this problem that achieves an regret guarantee, where is the delay window, as demonstrated by our theoretical analysis. Experiments on our constructed dataset show that our method consistently outperforms all baselines, confirming its effectiveness. Currently, our method assumes a stable parameter for each user. Accounting for the evolution of the utility pattern remains an interesting direction for future work.
Benchmark Construction Details
Prompts in Dataset Construction
In this section, we provide the detailed prompts used in the construction of the dataset. For the stages up to and including dialogue generation, we use the same prompts as In et al. [23] and refer readers to that paper for details.
Retrieval Trigger Prompt
You are deciding, on behalf of a memory-augmented assistant, whether responding well to a user’s message requires recalling something from an earlier conversation with this same user.
User’s message:
{user_content}
First, decide: does responding well to this message require recalling a specific fact, preference, plan, or detail the user has shared before – as opposed to being answerable from this message alone or from general knowledge?
If a memory lookup is needed, compose a short, self-contained search query capturing specifically what needs to be recalled – not a copy of the whole message, just the retrieval-relevant part.
Return strict JSON only, no other text:
{{"query_needed": true or false, "query": "<query text, or empty string if not needed>"}}
Retrieval Verification Prompt
You are judging whether retrieved memory facts are potentially helpful to respond to a user’s message in an ongoing conversation.
User message:
{query_text}
Candidate fact:
{candidate}
For each candidate, decide whether it is potentially helpful to respond well to this message. A fact is necessary if omitting it would make the response worse in any of these ways: - Factually wrong or incomplete given what the user has told you - Generic or one-size-fits-all where a tailored response is possible - Inconsistent with a preference, constraint, or decision the user has already established - Missing personalization the user would reasonably expect, given they already shared this
A fact is NOT necessary if it is merely on the same topic or in the same domain as the message, but doesn’t actually change what a good response would say – e.g. it’s superseded, tangential, or the message doesn’t call for that level of detail.
Being topically related is not sufficient on its own, but genuine personalization value (not just factual correctness) does count as necessary. If a candidate is a close call, prefer to keep it – this check does not need to be the final word.
Return strict JSON only, with the result and your reasoning:
{{"helpful": <yes|no>, "reasoning": "<your reasoning>"}}
(empty list if none are necessary)
Retrieval Recall Prompt
You are judging retrieved memory facts against a user’s message in an ongoing conversation. None of these facts individually scored as a strong match, but they may still matter in combination.
User message:
{query_text}
Candidate fact:
{format_candidates(candidates)}
Is there any subset of these facts that, used together, would be useful or necessary to respond to the user’s message? A single fact by itself not being a strong match does not rule out a combination of two or more being relevant.
Return strict JSON only, no other text:
{{"useful_entry_ids": ["<id>", ...]}}
(empty list if no combination is useful)
Quality Assessment Prompt
You are checking whether a specific piece of background information was actually used in an assistant’s reply within an ongoing conversation.
Conversation so far:
{session_prefix}
Background fact under test:
{fact_content}
Assistant’s reply:
{response}
Classify how much the reply draws on that specific fact:
- contains info from fact: the reply includes specific content, details, or claims that come from this fact (not just a generic reply that happens to be compatible with it).
- weakly related: the reply touches the same general topic as the fact but doesn’t actually use its specific content.
- irrelevant: the reply shows no sign of drawing on this fact at all.
Return strict JSON only, no other text:
{{"incorporation": "<contains_info_from_fact|weakly_related|irrelevant>"}}
Meta Evaluation
In this section, we conduct experiments to verify that the labels produced by the introduced pipeline genuinely reflect the actual utility during later interaction, rather than merely being an artifact of the selected memory system and LLM-judge.
Method. We sample collection of probes (i.e., user’s prompt) with valid retrieval hits. For each sample, we sample one judge-confirmed fact and one unconfirmed candidate, either not retrieved or rejected by the LLM-judge. For each sampled fact, we place it in the context of an LLM (we used gpt-5-mini here) and draw completions at non-zero temperature. For each generated response, we employ gpt-5-mini as a separate judge model to decide if the generated response related to the candidate fact: contains the fact, weakly related or irrelevant, and mapping to a score within and average over the responses. For the incorporation level test, we conduct a Wilcoxon signed-rank test over all pairs of (probe, average score of confirmed fact, average score of unconfirmed fact), and report the -value, effect size , and the 95% confidence interval of the scores.
Results. We sampled 5 users and pooled all matched confirmed and unconfirmed pairs across the five evaluated users, of which the results are presented in Table 4. The pooled results show that, compared to unconfirmed facts, confirmed facts are significantly more incorporated into the responses. Moreover, a paired Wilcoxon signed-rank test on the matched per-probe scores rejects the null of no difference (, ) with a large matched-pairs rank-biserial effect size (), indicating a statistical significance. Moreover, when breaking down to the per-user results, we find that all of these results agree with the pooled results. For every user, confirmed facts are incorporated into responses much more often than unconfirmed facts. Mean scores range from 0.372 to 0.600 for confirmed facts and from 0.077 to 0.167 for unconfirmed facts, leading to a per-user gap of 0.23 to 0.43. Moreover, the effect size is at least 0.75 and for all users, indicating that the difference stays significant across five users, showing that the pooled result is not driven by any single user: facts with positive labels are consistently used in the responses.
Table 4: Per-user fact-incorporation scores (mean, with 95% bootstrap CI) for confirmed vs. unconfirmed target facts, and the paired Wilcoxon test comparing them within each user. Reported as a robustness check on the pooled result, not as independent significance tests.
| User | Confirmed | Unconfirmed | |||
| 0045d22a | 12 | 0.600 [0.42, 0.78] | 0.167 [0.03, 0.33] | 1.00 | |
| 0097794e | 29 | 0.510 [0.36, 0.66] | 0.155 [0.07, 0.26] | 0.75 | |
| 009850d8 | 18 | 0.372 [0.20, 0.55] | 0.144 [0.02, 0.31] | 1.00 | |
| 00aefb8e | 32 | 0.456 [0.32, 0.60] | 0.091 [0.03, 0.18] | 0.90 | |
| 00e85c7f | 22 | 0.482 [0.35, 0.62] | 0.077 [0.01, 0.15] | 0.95 | |
| Pooled | 113 | 0.477 [0.40, 0.55] | 0.121 [0.08, 0.17] | 0.88 |
Table 4. Per-user fact-incorporation scores (mean, with 95% bootstrap CI) for confirmed vs. unconfirmed target facts, and the paired Wilcoxon test comparing them within each user. Reported as a robustness check on the pooled result, not as independent significance tests.
Statistics of the Constructed Benchmark
Tables 5 and 6 summarize some basic statistics of the constructed dataset. We highlight several notable properties that shape the gating problem.
Sparsity of Utilized Facts. On average, only 14.2% of a user’s facts are utilized in PerMemBench-S and 19.9% in PerMemBench-L. Even the user with the highest ratio reaches only 23.6% and 25.6%, respectively. In other words, for typical user, more than three quarters of the extracted facts are never used to answer a later query. Consequently, a policy that stores every fact fills a limited memory bank mostly with facts that are never used, and exhausts the bank capacity quickly. This leaves substantial room for a gating policy that learns to skip un-needed facts.
| Metric | Mean | Median | Min | Max | Std |
| Sessions per uuid | 54.25 | 57 | 36 | 70 | 9.93 |
| Total entries per uuid | 856.5 | 894 | 474 | 1295 | 203.58 |
| Entries with valid hits per uuid | 124.5 | 122 | 45 | 241 | 56.93 |
| Hit rate (hit entries / total entries) | 0.142 | 0.140 | 0.064 | 0.236 | 0.047 |
| Avg delay-to-first-hit (sessions) | 13.47 | 13.02 | 6.95 | 23.2 | 3.76 |
Table 5. Per-user statistics of PerMemBench-S, computed over the 20 users. Delay-to-first-hit is measured in sessions from extraction to the first valid retrieval hit.
| Metric | Mean | Median | Min | Max | Std |
| Sessions per uuid | 150.35 | 153 | 94 | 193 | 30.84 |
| Total entries per uuid | 2449.65 | 2435 | 1378 | 3341 | 550.39 |
| Entries with valid hits per uuid | 493.9 | 518 | 225 | 780 | 170.45 |
| Hit rate (hit entries / total entries) | 0.199 | 0.203 | 0.113 | 0.256 | 0.043 |
| Avg delay-to-first-hit (sessions) | 30.44 | 28.64 | 19.38 | 41.08 | 5.86 |
Table 6. Per-user statistics of PerMemBench-L, computed over the 20 users. Delay-to-first-hit is measured in sessions from extraction to the first valid retrieval hit.
Relatively Long Delay of Feedback. On average, a utilized fact receives its first valid hit 13.47 sessions after extraction in PerMemBench-S and 30.44 sessions in PerMemBench-L. These delays are roughly a quarter and a fifth of the average history length, respectively, and they grow with the length of the history rather than vanishing. With about 16 facts extracted per session on both benchmarks, this corresponds to several hundred subsequent facts, which exceeds some of the memory budgets we evaluate. This indicates that, feedback on an added fact arrives only after a substantial fraction of the interaction has passed, and might even get evicted before a meaningful signal is observed. Thus, the delay presents as an essential source of hardness for learning and motivates both the delay-aware estimator in Algorithm 1 and the warm start from other users’ data.
Experiment Details
Prompts of LLM-Based Methods
In this section, we provide the details of the prompts we used for LLM-greedy gating and LLM-context-aware gating. For each method, we consider two prompt templates: one directly adapted from In et al. [23], and a fine-grained version that takes the remaining capacity of the memory bank into consideration.
Greedy. At each fact, the LLM receives the content of the current fact and outputs a binary decision.
LLM-Greedy Gating Prompt (In et al., [23])
You are a memory policy agent. Decide whether this fact should be stored in long-term memory.
## Facts
{fact.get("content", "")}
store = true: durable, worth-storing information about the user – part of an ongoing project, recurring goal, preference, or constraint. store = false: transient fact – trivial, one-off, or self-contained with no lasting relevance.
Respond ONLY with:
{{"store": <true|false>}}

Figure 6.
You are the admission gate for a long-term memory bank in a memory-augmented assistant. The bank has a hard capacity limit – every fact you admit competes with every other fact for a slot.
{capacity_block(history)}
{GATING_RUBRIC}
Fact:
{fact.get("content", "")}
First briefly note which KEEP or DROP category the fact best matches, then decide.
Return strict JSON only, no other text:
{{"category": "<short KEEP/DROP category label>", "store": true or false}}
Context-Aware. Before prediction, the current session is summarized in 1–2 sentences and appended to a running summary buffer. At each session, the LLM receives the current dialogue alongside the most recent K session summaries as historical context.

Figure 7.
You are a memory policy agent. Decide whether this fact should be stored in long-term memory.
Recent Session Summaries
{history_summaries}
Current Session Dialogue
{current_dialogue}
Fact
{fact.get("content", "")}
store = true: durable, worth-storing information about the user – part of an ongoing project, recurring goal, preference, or constraint. store = false: transient fact – trivial, one-off, or self-contained with no lasting relevance.
Respond ONLY with:
{{"store": <true|false>}}

Figure 8.
You are the admission gate for a long-term memory bank in a memory-augmented assistant. The bank has a hard capacity limit – every fact you admit competes with every other fact for a slot.
{capacity_block(history)}
{GATING_RUBRIC}
Recent Session Summaries
{history_summaries}
Current Session Dialogue
{current_dialogue}
Fact:
{fact.get("content", "")}
First briefly note which KEEP or DROP category the fact best matches, then decide.
Return strict JSON only, no other text:
{{"category": "<short KEEP/DROP category label>", "store": true or false}}
The contents of the gating rubric and capacity block are given as follows.

Figure 9.
Gating Rubric
KEEP (durable, user-specific – worth recalling in a future conversation):
Concrete preferences ("prefers X over Y", likes/dislikes)
Standing plans, goals, or decisions the user has committed to
Constraints or limitations (budget, health, schedule, skill level, access)
Relationships, roles, or people/pets recurring in the user’s life
Stable biographical or contextual facts (job, location, ongoing projects) DROP (low value – not worth the slot):
Small talk, pleasantries, filler, or meta-conversation
One-off transient state ("is tired right now", "it's raining today")
Generic statements that aren’t specific to this user
Speculative or hypothetical musings the user hasn’t actually decided on
Facts that are near-duplicates of something already obviously established
Capacity Block
If vacant
Capacity check: the memory bank has plenty of free room right now, so bias toward KEEPING. Admit anything that plausibly fits a KEEP category below, even if it’s only moderately durable or specific – only DROP facts that clearly belong in the DROP list.
If somewhat vacant
Capacity check: the memory bank is filling up, so be selective. Admit only facts that clearly fit a KEEP category below with a reasonable chance of mattering later – DROP anything vague, borderline, or that fits the DROP list.
If space limited
Capacity check: the memory bank is nearly full, so be highly selective. Admit only facts you are confident are high-value KEEPs (firm decisions, explicit constraints or preferences the user is likely to reference again, major ongoing plans) – DROP anything minor, speculative, or merely plausible.
Hyper-parameters of Proposed Methods
In this section, we provide the implementation details and hyper-parameters of linear gating methods. We use OpenAI text-embedding-3-small to obtain an embedding of each fact and treat the embedding as the linear feature. For Warm-Start UCB and Pre-trained Scorer, for each given test user, we first fit a linear parameter on a training set composed of 15 other users randomly selected from the pool of 19 users. We then select the hyper-parameters by validating on another 4 users. We keep the routine of Algorithm 1 unchanged, while making the confidence radii and the gating threshold as hyper-parameters. We further simplify the initialization of the pre-trained covariance matrix by setting it to identity matrix , for Warm-Start UCB.
For Cold-Start UCB, we consider the confidence radius and the gating threshold and . For each fact, we wait for sessions to see if there is at least one valid retrieval. We consider for PerMemBench-S and for PerMemBench-L, to account for the longer delay. We report the best performance achieved by the combination of hyper-parameters that achieves the highest micro RHR.
For Pre-trained Scorer, we sweep the gating threshold . For UCB with warm start, we adapt the gating threshold by considering , where is the best validated value for Pre-trained Scorer. We further consider the confidence radius . For PerMemBench-L, we consider and . For PerMemBench-S, we account for the smaller amount of pre-training data and the shorter delay, and therefore consider and .
Additional Experiment Results
This section reports the learning-dynamics and pre-training pool-size results omitted from § 5.3. Figure 4 and Figure 5 show the per-decile F1 gain over the Universal baseline and the effect of the pre-training pool size on PerMemBench-S, respectively. The same set of results for the remaining budgets of PerMemBench-L (i.e., 250 and 800) is presented in Figure 3.
Figure 3. Learning dynamics (3(a), 3(b)) and effect of the pre-training pool size (3(c), 3(d)) on PerMemBench-L for the remaining memory budgets . Shaded regions denote the 95% CI over all users.
Figure 4. Learning dynamics on PerMemBench-S: F1 gain over the Universal baseline in each session-position decile under memory budgets . Shaded regions denote the 95% CI over all users.

Figure 5. Effect of the pre-training pool size on PerMemBench-S: best micro- and macro-averaged RHRs under .
On PerMemBench-L, the additional budgets reproduce the trends in § 5.3. Pre-trained Scorer gives an immediate gain that shrinks in later deciles. Warm-Start UCB separates from it at later deciles. Cold-Start UCB remains close to the Universal baseline. RHRs also increase monotonically with the pool size under both budgets, improving by roughly 3–4 points from one to fifteen pre-training users.
On PerMemBench-S, the same qualitative picture holds, and pre-training again gives a positive gain from the first decile. Warm-Start UCB and Pre-trained Scorer both outperform Cold-Start UCB for most of the interaction, and RHRs with fifteen pre-training users exceed those with a single user under every budget. The results are, however, noticeably noisier when the interaction history is short. In Figure 4, the confidence bands of Warm-Start UCB and Pre-trained Scorer largely overlap, and a clear separation between them appears only at . Cold-Start UCB fluctuates strongly and drops sharply in the ninth decile under all four budgets before recovering. In Figure 5, performance does not increase monotonically with the pool size: it dips at a pool size of five for and and stays nearly flat between two and ten users for and . This is because, with a substantially shorter interaction history, the online estimator does not collect sufficient feedback to converge, and the offline pre-training pool is also much smaller. We therefore regard PerMemBench-L as the more reliable testbed for studying learning dynamics, and we report it in the main text.
Discussion of Assumption 4.5
In this section, we provide a two-step justification of Assumption 4.5. The first step controls the variation of the current user’s parameter around a population center, while the second controls the error incurred when estimating this population center from other users’ data. Let denote the population-level parameter. Suppose first that the current user’s parameter is concentrated around in the geometry induced by . In particular, assume that
The cross-user predictability observed in § 3.2 provides empirical motivation for the existence of such a shared population component. At the same time, the gap between the within-user and leave-one-user-out performance suggests that need not be zero: it captures the irreducible heterogeneity between the current user and the population.
We next justify that the population center can be estimated accurately from other users’ data. Suppose that the pretraining sample satisfies
where includes both observation noise and zero-mean variation among the pretraining users. Let
and suppose for some . Consider the ridge estimator with regularization to be determined later,
Standard random-design ridge-regression results, such as Hsu et al. [21], Theorem 2, imply that, when the sample size is sufficiently large4, with probability at least ,
up to lower-order terms arising from estimating the covariance matrix, where
For the idealized choice , which satisfies , (D.2) gives
with probability at least . More generally, the same conclusion holds when is an empirical covariance estimate that is spectrally equivalent to . Moreover, when is sufficiently small and sufficiently large, the ridge bias is dominated by the stochastic error, leading to a sufficiently small error .
On the intersection of the events in (D.1) and (D.3), the triangle inequality gives
Therefore, we recover Assumption 4.5 by setting and :
Remark D.1. While the estimation component decreases as the amount of pretraining data grows, the population component captures genuine user heterogeneity and generally does not vanish with .
Missing Proof from Section 4
In this section, we provide the proof of Theorem 4.7. We first define the following filtration. For , we consider generated by
where is defined as is if and otherwise . For , we have , , and .
Proof of Optimism
Lemma E.1. Let the warm-start event . Then conditional on , with probability at least , simultaneously for all ,
where . Consequently, if , then the preceding event holds with probability at least .
Proof of Lemma E.1. Let denote the set of rounds up to time in which the learner plays action add. We partition into the completed and pending sets
For every , the -round observation window has elapsed, and hence
Because and is conditionally independent of given , we have
Therefore, defining , we obtain a conditionally mean-zero and -sub-Gaussian noise sequence. Now define the completed-sample design matrix and its corresponding ridge estimator
Subtracting gives
Since , the prior-mismatch term satisfies, on ,
We next bound the determinant term in the self-normalized inequality. Since and is -sub-Gaussian with condition on , we can apply Lemma F.2, which leads to that with probability at least $1-\deltat\ge 0
Since and , Lemma F.3 leads to
Combining these estimation therefore implies that, with probability at least , simultaneously for all ,
Combining the preceding inequality with the prior-mismatch bound yields
simultaneously for all . It remains to translate to . By the definition of Algorithm 1, we know that , which leads to
Since , we know that
Therefore, the triangle inequality gives
Because , we have . Consequently,
For each , both and belong to . Therefore,
The triangle inequality then gives
Combining the last three displays, we conclude that, simultaneously for all ,
This proves the conditional statement. Finally, combining the online concentration event with proves the unconditional probability bound .
Main Theorem
Proof of Theorem 4.7. Throughout the proof, we work on the good event from Lemma E.1. On this event, simultaneously for all ,
where . We first show that the index is optimistic for . Fix any . By Cauchy–Schwarz and the definition of ,
Recalling the computation of , it follows that
Suppose first that . By (★), , so Algorithm 1 chooses , which agrees with the oracle policy. Thus, the algorithm never incorrectly skips a context that the oracle would add. Therefore, the only case in which the algorithm incurs nonzero regret is
In this case, the decision rule implies , and the per-step regret is given by
Moreover, we see that
Consequently,
Now let denote the set of rounds with action add. Summing the preceding inequality gives
Substituting the definition of , we decompose the sum as
We first bound (I). Since and , we see that . This allows us to apply the elliptical-potential lemma (Lemma F.1) to the subsequence of added contexts, which yields
where the last inequality holds due to Lemma F.3. Therefore, Cauchy–Schwarz implies
It follows that
We next bound (II). Applying termwise yields
For every , the pending set contains at most elements. Hence,
To bound , we exchange the order of summation. Fix a round such that . The term involving appears only for rounds satisfying and , which requires . Thus, it appears at most times. Moreover, for every such , we have and therefore
This immediately implies that
Combining the bounds for and gives
Finally, combining the bounds for and , we conclude that, on ,
By Lemma E.1, the event holds with probability at least conditional on the warm-start event . Since , the claimed regret bound holds with probability at least .
It remains to pick a proper . For notational convenience, define and . We start with
We first derive the warm-start bound. Using gives . Consequently, the warm-start contribution satisfies
Meanwhile, as , we see that ; thus, the remaining term vanishes:
Taking the infimum over therefore yields
We next derive the learning-based bound. Suppose and choose
When is sufficiently small such that , this reduces to . For this choice, we see that and . Substituting this choice into (E.1) gives
where the last inequality suppresses logarithmic factors in , , , and . Combining this bound with the warm-start bound yields
which gives the desired bound.
Finally, we characterize the phase transition so that can be selected in a principled way. The boundary between the two bounds is determined by . Letting , the boundary equation becomes . Solving this equation with respect to gives its positive solution
Therefore,
Therefore, setting when and leads to the rate in (E.2). □
Supplementary Lemmas
Lemma F.1 ((Lemma 11, Abbasi-Yadkori et al. 2011)). Let , and for define
where is a (deterministic) positive definite matrix. Then
If, in addition, for all , then
Lemma F.2 ((Theorem 1, Abbasi-Yadkori et al. 2011)). Let be a filtration. Let be a real-valued stochastic process such that is -measurable and, for some , is conditionally -sub-Gaussian given , i.e.
Let be an -valued stochastic process such that is -measurable (i.e. may depend on the past but not on ). Let be any deterministic positive definite matrix. For any , define
Then, for any , with probability at least , for all simultaneously,
The following lemma provides the calculation of the log-determinant term appearing in Lemma F.1 and Lemma F.2.
Lemma F.3. Let , and let satisfy for every . Define . Then, for every ,
Proof. Define
Since , we have , and hence
Let be the eigenvalues of , then we see that
Applying AM–GM inequality,
which finishes the proof.
References
- [1]Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
- [2]Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Conference on Learning Theory, pp. 23–35. PMLR, 2015.arxiv.org/abs/1502.07617
- [3]Byeongwoo An, Kapilan Balagopalan, Hyowon Wi, Sehwa Jeong, Jiun Jeong, Kyoungseok Jang, Noseong Park, Gi-Soo Kim, and Kwang-Sung Jun. Efficient algorithms for contextual apple tasting with log-loss. In Decision-Making from Offline Datasets to Online Adaptation: Black-Box Optimization to Reinforcement Learning, 2026.
- [4]Gábor Bartók and Csaba Szepesvári. Partial monitoring with side information. In International Conference on Algorithmic Learning Theory, pp. 305–319. Springer, 2012.DOI
- [5]Gábor Bartók, Dean P Foster, Dávid Pál, Alexander Rakhlin, and Csaba Szepesvári. Partial monitoring—classification, regret bounds, and algorithms. Mathematics of Operations Research, 39(4):967–997, 2014.DOI
- [6]Yahav Bechavod and Aaron Roth. Individually fair learning with one-sided feedback. In International Conference on Machine Learning, pp. 1954–1977. PMLR, 2023.arxiv.org/abs/2206.04475
- [7]Yahav Bechavod, Katrina Ligett, Aaron Roth, Bo Waggoner, and Steven Wu. Equal opportunity in online classification with partial feedback. Advances in Neural Information Processing Systems, 32, 2019.arxiv.org/abs/1902.02242
- [8]Ilai Bistritz, Zhengyuan Zhou, Xi Chen, Nicholas Bambos, and Jose Blanchet. No weighted-regret learning in adversarial bandits with delays. Journal of Machine Learning Research, 23(139):1–43, 2022.arxiv.org/abs/2103.04550
- [9]Jose Blanchet, Renyuan Xu, and Zhengyuan Zhou. Delay-adaptive learning in generalized linear contextual bandits. Mathematics of Operations Research, 49(1):326–345, 2024.arxiv.org/abs/2003.05174
- [10]Leonardo Cella, Alessandro Lazaric, and Massimiliano Pontil. Meta-learning with stochastic linear bandits. In International Conference on Machine Learning, pp. 1360–1370. PMLR, 2020.arxiv.org/abs/2005.08531
- [11]Nicolò Cesa-Bianchi, Claudio Gentile, and Yishay Mansour. Delay and cooperation in nonstochastic bandits. Journal of Machine Learning Research, 20(17):1–38, 2019.
- [12]Tommaso Cesari and Roberto Colomboni. Two-action apple tasting with switching costs. arXiv preprint arXiv:2606.03851, 2026.
- [13]Zachary Chase and Idan Mehalel. Deterministic apple tasting. In Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pp. 888–923. PMLR, 30 Jun–04 Jul 2025.arxiv.org/abs/2410.10404
- [14]Prateek Chhikara, Dev Khant, Saket Aryan, Taranjeet Singh, and Deshraj Yadav. Mem0: Building production-ready ai agents with scalable long-term memory. arXiv preprint arXiv:2504.19413, 2025.arxiv.org/abs/2504.19413
- [15]James A Grant and David S Leslie. Apple tasting revisited: Bayesian approaches to partially monitored online binary classification. arXiv preprint arXiv:2109.14412, 2021.arxiv.org/abs/2109.14412
- [16]Andras Gyorgy and Pooria Joulani. Adapting to delays and data in adversarial multi-armed bandits. In International Conference on Machine Learning, pp. 3988–3997. PMLR, 2021.arxiv.org/abs/2010.06022
- [17]Keegan Harris, Chara Podimata, and Steven Z Wu. Strategic apple tasting. Advances in Neural Information Processing Systems, 36:79918–79945, 2023.arxiv.org/abs/2306.06250
- [18]David P Helmbold, Nick Littlestone, and Philip M Long. Apple tasting and nearly one-sided learning. In Proceedings., 33rd Annual Symposium on Foundations of Computer Science, pp. 493–502. IEEE, 1992.DOI
- [19]David P Helmbold, Nicholas Littlestone, and Philip M Long. Apple tasting. Information and Computation, 161(2):85–139, 2000.DOI
- [20]Benjamin Howson, Ciara Pike-Burke, and Sarah Filippi. Delayed feedback in generalised linear bandits revisited. In International Conference on Artificial Intelligence and Statistics, pp. 6095–6119. PMLR, 2023.arxiv.org/abs/2207.10786
- [21]Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression. Foundations of Computational Mathematics, 14(3):569–600, 2014.
- [22]Yuyang Hu, Shichun Liu, Yanwei Yue, Guibin Zhang, Boyang Liu, Fangyi Zhu, Jiahang Lin, Honglin Guo, Shihan Dou, Zhiheng Xi, et al. Memory in the age of ai agents. arXiv preprint arXiv:2512.13564, 2025.arxiv.org/abs/2512.13564
- [23]Yeonjun In, Wonjoong Kim, Sangwu Park, Kanghoon Yoon, and Chanyoung Park. Personalize-then-store: Benchmarking and learning personalized memory for long-horizon agents. arXiv preprint arXiv:2605.25535, 2026.arxiv.org/abs/2605.25535
- [24]Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Online learning under delayed feedback. In International conference on machine learning, pp. 1453–1461. PMLR, 2013.arxiv.org/abs/1306.0686
- [25]Tal Lancewicki, Shahar Segal, Tomer Koren, and Yishay Mansour. Stochastic multi-armed bandits with unrestricted delay distributions. In International Conference on Machine Learning, pp. 5969–5978. PMLR, 2021.arxiv.org/abs/2106.02436
- [26]Mingfei Lu, Mengjia Wu, Feng Liu, Jiawei Xu, Weikai Li, Haoyang Wang, Zhengdong Hu, Ying Ding, Yizhou Sun, Jie Lu, et al. Choosing how to remember: Adaptive memory structures for llm agents. arXiv preprint arXiv:2602.14038, 2026.arxiv.org/abs/2602.14038
- [27]Saeed Masoudian, Julian Zimmert, and Yevgeny Seldin. A best-of-both-worlds algorithm for bandits with delayed feedback. Advances in Neural Information Processing Systems, 35:11752–11762, 2022.arxiv.org/abs/2206.14906
- [28]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.arxiv.org/abs/2310.08560
- [29]Joon Sung Park, Joseph O’Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S Bernstein. Generative agents: Interactive simulacra of human behavior. In Proceedings of the 36th annual acm symposium on user interface software and technology, pp. 1–22, 2023.arxiv.org/abs/2304.03442
- [30]Amit Peleg, Naama Pearl, and Ron Meir. Metalearning linear bandits by prior update. In International Conference on Artificial Intelligence and Statistics, pp. 2885–2926. PMLR, 2022.arxiv.org/abs/2107.05320
- [31]Vinod Raman, Unique Subedi, Ananth Raman, and Ambuj Tewari. Apple tasting: Combinatorial dimensions and minimax rates. In The Thirty Seventh Annual Conference on Learning Theory, pp. 4358–4380. PMLR, 2024.arxiv.org/abs/2310.19064
- [32]Alireza Rezazadeh, Zichao Li, Wei Wei, and Yujia Bao. From isolated conversations to hierarchical schemas: Dynamic tree memory representation for llms. In International Conference on Learning Representations, volume 2025, pp. 990–1023, 2025.arxiv.org/abs/2410.14052
- [33]Ofir Schlisselberg, Ido Cohen, Tal Lancewicki, and Yishay Mansour. Delay as payoff in mab. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 20310–20317, 2025.arxiv.org/abs/2408.15158
- [34]Ofir Schlisselberg, Tal Lancewicki, Peter Auer, and Yishay Mansour. Improved best-of-both-worlds regret for bandits with delayed feedback. Advances in Neural Information Processing Systems, 38:2035–2072, 2026a.arxiv.org/abs/2505.24193
- [35]Ofir Schlisselberg, Mengxiao Zhang, and Yishay Mansour. Near-optimal stochastic linear bandits with delay. arXiv preprint arXiv:2606.16656, 2026b.arxiv.org/abs/2606.16656
- [36]Xiaolong Sun, Qichao Wang, Hangyu Li, and Liang Chen. Verifiable memory: Learning unified memory management with local and global verifiers for large language model agents. arXiv preprint arXiv:2608.03137, 2026.arxiv.org/abs/2608.03137
- [37]Zhen Tan, Jun Yan, I-Hung Hsu, Rujun Han, Zifeng Wang, Long Le, Yiwen Song, Yanfei Chen, Hamid Palangi, George Lee, et al. In prospect and retrospect: Reflective memory management for long-term personalized dialogue agents. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 8416–8439, 2025.arxiv.org/abs/2503.08026
- [38]Yifu Tang, Yingfei Wang, and Zeyu Zheng. Stochastic multi-armed bandits with strongly reward-dependent delays. In International Conference on Artificial Intelligence and Statistics, pp. 3043–3051. PMLR, 2024.
- [39]Tobias Sommer Thune, Nicolò Cesa-Bianchi, and Yevgeny Seldin. Nonstochastic multiarmed bandits with unrestricted delays. Advances in Neural Information Processing Systems, 32, 2019.arxiv.org/abs/1906.00670
- [40]Dirk Van Der Hoeven, Lukas Zierahn, Tal Lanczewicki, Aviv Rosenberg, and Nicolò Cesa-Bianchi. A unified analysis of nonstochastic delayed feedback for combinatorial semi-bandits, linear bandits, and mdps. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1285–1321. PMLR, 2023.
- [41]Claire Vernade, Olivier Cappé, and Vianney Perchet. Stochastic bandit models for delayed conversions. In UAI, 2017.arxiv.org/abs/1706.09186
- [42]Claire Vernade, Alexandra Carpentier, Tor Lattimore, Giovanni Zappella, Beyza Ermis, and Michael Brueckner. Linear bandits with stochastic delayed feedback. In International Conference on Machine Learning, pp. 9712–9721. PMLR, 2020.
- [43]Yancheng Wang, Ziyan Jiang, Zheng Chen, Fan Yang, Yingxue Zhou, Eunah Cho, Xing Fan, Yanbin Lu, Xiaojang Huang, and Yingzhen Yang. Remind: Large language model powered agent for recommendation. In Findings of the Association for Computational Linguistics: NAACL 2024, pp. 4351–4364, 2024a.arxiv.org/abs/2308.14296
- [44]Zihao Wang, Shaofei Cai, Anji Liu, Yonggang Jin, Jinbing Hou, Bowei Zhang, Haowei Lin, Zhaofeng He, Zilong Zheng, Yaodong Yang, et al. Jarvis-1: Open-world multi-task agents with memory-augmented multimodal language models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 47(3):1894–1907, 2024b.arxiv.org/abs/2311.05997
- [45]Zora Zhiruo Wang, Jiayuan Mao, Daniel Fried, and Graham Neubig. Agent workflow memory. In Forty-second International Conference on Machine Learning, 2025.arxiv.org/abs/2409.07429
- [46]Wujiang Xu, Zujie Liang, Kai Mei, Hang Gao, Juntao Tan, and Yongfeng Zhang. A-mem: Agentic memory for llm agents. Advances in Neural Information Processing Systems, 38:17577–17604, 2026.arxiv.org/abs/2502.12110
- [47]Sikuan Yan, Xiufeng Yang, Zuchao Huang, Ercong Nie, Zifeng Ding, Zonggen Li, Xiaowen Ma, Jinhe Bi, Kristian Kersting, Jeff Z Pan, et al. Memory-r1: Enhancing large language model agents to manage and utilize memories via reinforcement learning. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 12805–12825, 2026.
- [48]Ke Yang, Zixi Chen, Xuan He, Jize Jiang, Michel Galley, Chenglong Wang, Jianfeng Gao, Jiawei Han, and ChengXiang Zhai. Plugmem: A task-agnostic plugin memory module for LLM agents. In Forty-third International Conference on Machine Learning, 2026.arxiv.org/abs/2603.03296
- [50]Mengxiao Zhang, Yuheng Zhang, Olga Vrousgou, Haipeng Luo, and Paul Mineiro. Practical contextual bandits with feedback graphs. Advances in Neural Information Processing Systems, 36:30592–30617, 2023.arxiv.org/abs/2302.08631
- [51]Longtao Zheng, Rundong Wang, Xinrun Wang, and Bo An. Synapse: Trajectory-as-exemplar prompting with memory for computer control. In International Conference on Learning Representations, volume 2024, pp. 19036–19066, 2024.arxiv.org/abs/2306.07863
- [52]Wanjun Zhong, Lianghong Guo, Qiqi Gao, He Ye, and Yanlin Wang. Memorybank: Enhancing large language models with long-term memory. In Proceedings of the AAAI conference on artificial intelligence, volume 38, pp. 19724–19731, 2024.arxiv.org/abs/2305.10250
- [53]Zhengyuan Zhou, Renyuan Xu, and Jose Blanchet. Learning in generalized linear contextual bandits with stochastic delays. Advances in Neural Information Processing Systems, 32, 2019.
- [54]Zijian Zhou, Ao Qu, Zhaoxuan Wu, Sunghwan Kim, Alok Prakash, Daniela Rus, Bryan Kian Hsiang Low, and Paul Liang. Mem1: Learning to synergize memory and reasoning for efficient long-horizon agents. In International Conference on Learning Representations, volume 2026, pp. 58413–58438, 2026.arxiv.org/abs/2506.15841
- [55]Xizhou Zhu, Yuntao Chen, Hao Tian, Chenxin Tao, Weijie Su, Chenyu Yang, Gao Huang, Bin Li, Lewei Lu, Xiaogang Wang, et al. Ghost in the minecraft: Generally capable agents for open-world environments via large language models with text-based knowledge and memory. arXiv preprint arXiv:2305.17144, 2023.arxiv.org/abs/2305.17144
- [56]Julian Zimmert and Yevgeny Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In International Conference on Artificial Intelligence and Statistics, pp. 3285–3294. PMLR, 2020.arxiv.org/abs/1910.06054


