Eigen Memory Trees
Authors: Mark Rucker
Jordan T. Ash
John Langford
Paul Mineiro
Ida Momennejad
Venue: Submitted to ICLR 2023 (2023)
Keywords: Episodic Memory
Contextual Bandits
Sequential Learning

Abstract: This work introduces the Eigen Memory Tree (EMT), a novel online memory model for sequential learning scenarios. EMTs store data at the leaves of a binary tree, and route new samples through the structure using the principal components of previous experiences, facilitating efficient (logarithmic) access to relevant memories. We demonstrate that EMT outperforms existing online memory approaches, and provide a hybridized EMT-parametric algorithm that enjoys drastically improved performance over purely parametric methods with nearly no downsides. Our findings are validated using 206 datasets from OpenML repository in both bounded and infinite memory budget situations. 

Under review as a conference paper at ICLR 2023
EIGEN MEMORY TREES
Anonymous authors Paper under double-blind review
ABSTRACT
This work introduces the Eigen Memory Tree (EMT), novel online memory model for sequential learning scenarios. EMTs store data at the leaves of bi- nary tree and route new samples through the structure using the principal com- ponents of previous experiences, facilitating efficient (logarithmicc access to rel- evant memories. We demonstrate that EMT outperforms existing online mem- ory approaches, and provide hybridized EMMT-parametri algorithm that enjoys drastically improved performance over purely parametric methods with nearly no downsides. Our findings are validated using 206 datasets from the OpenML repos- itory in both bounded and infinite memory budget situations.
INTRODUCTION
A sequential learning framework (also known as online or incremental learning (Hoi et al. 2021 Losing et al., 2018)) considers a setting in which data instances 2, IRd arrive incrementally. After each instance, the agent is required to make a decision from a set of [A] possibilities, a₂ E A. The agent then receives scalar feedback Y1 regarding the quality of the action, and the goal for the agent to learn mapping from to that maximizes the sum of all observed y/--
This general paradigm accommodates a wide array of well-studied machine learning scenarios. For example, in online supervised learning, A is a set of labels- the agent is required to predict label for each Tt, and the feedback yr. indicates the quality of the prediction.
In contextual bandit reinforcement learning setting, acts as context or state, is action, and y/ corresponds to reward provided by the environment. Contextual Bandits have proven useful in wide variety of settings; their properties extremely well studied (Langford & Zhang (007) and have tremendous theoretical and real-world applications (Bouneffouf et al. 2020).
Regardless of the particulars of the learning scenario, primary consideration is sample complexity. That is, how can we obtain the fighest-performen model given a fixed interaction budget? This often arises when agents only receive feedback corresponding to the chosen action a, i.e. partial feedback. Here, after an interaction with the environment, the agent does not get access to what the best action in hindsight would have been. As consequence, learners in cartial-feedbace setting need to explore different actions even for a fixed I, in order to discover optimal behavior.
Recent work reinforcement learning has demonstrated that episodic memory mechanisms can facilitate more efficient learning (Lengyel & Dayan 2007: Blundell et al., 2016; Pritzel et al. 2017 Hansen et al. 2018, Lin al. 2018 Zhu et al. 2020). Episodic memory (Tulving) 1972) refers to memory of specific past experiences (e.g., what did have for breakfast yesterday). This is in contrast to semantic memory, which generalizes across many experiences (e.g., what my favorite meal for breakfast). Semantic memory is functionally closer to parametric approaches to learning, which also rely on generalizations while discarding information about specific events or items.
This paper investigates the use of episodic memory for accelerating learning in sequential problems. We introduce Eigen Memory Trees (EMT), a model that stores past observations the leaves of a binary tree. Each leaf contains experiences that are somewhat similar to each other, and the EMT structured such that new samples are routed through the tree based on the statistical properties of previously encountered data. When the EMT is queried with new observation, this property affords an efficient way to compare it with only the most relevant memories. learned "scoring" function is used to identify the most salient memory in the leaf to be used for decision making.

---

Under review as a conference paper at ICLR 2023
Cells indicate the number of datasets in which the row algorithm beats the column algorithm with statistical significance. The stacked algorithm we propose (PEMT) has the most wins in each column as indicated by bold.
Table 1:
LEARN
QUERY
Update-scorer to
Search root to leaf
Insert
Predict-scorer
Split-leaf
Identify most similar memory
Parametric
PEMT
PCMT
Top-eigen
Return match most similar
EMT
CMT
for rouiing
PEMT
167
196
110
A schematic of the Eigen Memory Tree (EMT) algorithm. The outer boxes indicate the two operations supported by EMT, Learn and Query. The inner boxes show the high-level subroutines that occur to accomplish the outer operation.
Figure 1:
EMT
31
42
177
44
PCMT
4
156
192
75
CMT
7
11
10
17
Parametric
8
151
10
184
Specifically, this work
introduces the Eigen Memory Tree, an efficient tool for storing, accessing, and comparing memories to current observations (see Figure J
shows that the EMT gives drastically improved performance over comparable episodic memory data structures, and sometimes even outperforms parametric approaches that have explicit memory mechanism.
proposes simple combination EMT-parametric (PEMT) approach, which outperforms both purely parametric and EMT methods with nearly no downsides (see Table
In the following section, we introduce the Eigen Memory Tree and overview the algorithms required for storing and retrieving memories. A schematic of EMT and its high-level algorithms can be seen Figure With this in mind, Section describes related work.
Section 4 follows with an exhaustive set of experiments. demonstrating the superiority of EMT to previous episodic memory models and motivating the EMT-parametric (PEMT) method, a simple and powerful hybrid strategy for obtaining competitive performance sequential learning prob- lems. Importantly, we show that the PEMT performance advantage holds even when it is constrained to have fixed limit the number of memories it is allowed to store.
All experiments here consider the contextual bandit setting, but EMTs are applicable in broader domains well. This section continually references Table [ identifying which methods outper- form which other methods by statistically significant amount over all datasets and replicates. We consider substantial number of datasets from the OPe /Vanschoren al. 2014) repository.
Section summarizes our findings, discusses limitations, and overviews directions for future work.
EIGEN MEMORY TREE
As with episodic memory, EMT is structured around storing and retrieving exact memories. We formalize this notion as the self-consistency property: if a memory has been previously Inserted, then Query with the same key should return the previously inserted value. The self-consistency property encodes the assumption that the optimal memory to return, if possible, is an exact match for the current observation.
EMT is memory model with four key characteristics: (1) self-consistency, (2) incremental memory growth, (3) incremental query improvement via supervised feedback, and (4) sub-linear computa- tional complexity with respect to the number of memories in the tree. As we discuss in the literature review below, this combination of characteristics separates EMT from previous approaches.
Memory. EMT represents memories as mapping from keys to values, M = Rd R, where is the dimensionality of the context 2t, and zt E R corresponds to observed feedback. A query to the EMT requires 2; and returns a previously observed value ÿ E R from its bank of memories. EMT learning, which updates both the underlying data structure and the scoring mechanism, requires full (Ir,, ye) observation pair M.
2

---

Under review as a conference paper at ICLR 2023
Algorithm Primary Functions
1: class Node (router IR4, boundary R, left: Node, right: Node, M S Rd RR:
2: Initialize: rool Node()
3: Initialize: w + random vector in Rd
4: Initialize: f leaf capacity
5: function QUERY(Z E R
6: 71 4- rool
7: while is not leaf n. n.left if (n.router, æ) S nt.boundary else n.right
8: return arg W... PREDICTSCORER(C, Tm))
9: end function
function LEARN(E E IRd, y E IR)
11: < root
12: while n is not leaf n f- n.left if (n.router, a) S n.boundary else n.right
13: UPDATESCORER(Z:2)
14:
n.M <- n.M U (r,y) y)
Insert memory into leaf.
15:
if n. 2 then
16:
SPLITLEAF(z)
end if end function
18:
Data structure. The underlying data structure used by the EMT binary tree. The is composed of a set of nodes, N, each of which is either an internal node leaf node. If node N internal it possesses two child nodes (n.left E A and n.right N),, a decision boundary bounddd R. and top eigenvector n.router Rd The decision boundary and top eigenvector, as discussed later, are used to route queries through the tree. a node n is leaf node then will instead possess finite set of memories n.M = (ar, y) E Rd - R In addition to the nodes and routers EMT also possesses a single global scoring function responsible for selecting which memory to return given query and leaf node. This function is parameterised in by the weight vector R2
Learn. Newly acquired information is stored during the learning operation (Line T0 in Algo- rithm [}. which takes an item M and traverses the tree until a suitable insertion leaf is identified (Line 14 Algorithm[I] []. Immediately before insertion, the scoring function weights are updated such that the scores of the insertion leaf's memories improve with respect to the observed z, and yr
(Line 13
Algorithm M
Scorer. EMT's scorer, w. ranks candidate memories at query time. The scorer supports both
(2) Intuitively, the scorer can be thought of as dissimilarity metric, assigning small values to similar query pairs and large values dissimilar query pairs.
predictions (see Line [2 Algorithm 2 and updates (see Line [ [ Algorithm
pair of identical query vectors is guaranteed to result in score of 0, satisfying the self-consistency property mentioned earlier. This is achieved for any two xı and 22 by applying the scorer on the coordinate-wee absolute value difference between pairs, + [(x ((z));((e) ( which is all zeros the two contexts identical. Predictions are then made by linearly regressing this vector onto the scorer's 's weights, and clipping predictions (w, 2) such that the minimum is O. The clipping operation ensures that predictions will be even when weights are negative.
Updating the scoring function is done via ranking loss, which considers (1) (Thest Bhest), which is the memory-reward pair that would be retrieved by the scorer currently and (2) (Fane Dan), an alterna- tive memory in the same leaf that has a reward most similar to the current observation (omitting the retrieved memory Whes). If yalt gives a better prediction of the observed reward than Phest. we adjust the scorer to decrease the learned dissimilarity between aalt and the current target zt. Alternatively, the retrieved memory Ybest is closer to the observed reward, we do the opposite, emphasizing the similarity between and Æbest and making 2; and Zan dissimilar. Specifically, this is done by taking a gradient step with respect to an L2 loss that encourages more similar pairs to have a score near and more dissimilar pairs to have score near 1.

---

Under review as a conference paper at ICLR 2023
Level 1
Level 2
Level 3
Level 4
Figure A I-SNE visualization of EMT after training on OpenML's BNG (breast-w) dataset. Each point represents memory and is colored to indicate the node at which the memory stored. Each plot shows memo- ries colored by how they are allocated at the indicated level of the tree. The level of the tree considered increases by one from left to right, doubling the number of nodes considered (number of data paths from root to node).
Algorithm 2 Scorer Functions
function UPDATESCORER(M C IR x I. I R. YEE.EER R) (Ib y6) arg min (mm MEM PREDICTSCORER(C:20)) (Ta; Va) = arg min (em.
yml
if [//. 9/1 < Ve V/l then
+ (1 PE
ac
< w 17 Bhe
else if yb - Vd Yo Yi then
PREDDCCTSCORRRGGATT + (OOOERRC..""*+IIPEECECCCCCC""SS (1-PREDICCTSCORR(((5..))
ac
w 18
end if end function
function PREDICTSCORER(21 E RR, E Rd)
(1(=1), (x2)) 1=-1
Rd
return max(0, (w, 2))
> We clip for self-consistency purposes.
end function
Query. To predict we can call EMT's Query operation with Ie (see Line 5 in Algorithm
Queries to the EMT trigger a search over the internal data structure, beginning at the root node and routing through internal nodes until leaf is eventually reached. When the search procedure is presented with an internal node n, routing follows simple rule: if (n.router, xx) S n.boundary we proceed left, if not we proceed right (see Line Algorithm [] When we arrive at leaf the scorer then called identify the most similar memory available (see Line in in Algorithm T.
Eigen-router initialization. An important hyperparameter in the EMT is the maximum leaf ca- pacity c, which controls the number of memories stored in a single leaf node. Once the leaf reaches this capacity, the corresponding node is assigned a left and right child. and its memories are al- located across them. If с small, the tree extended frequently to accommodate new data, and when it is large, the tree grows more slowly. A large c allows many memories to be scored for particular query, which can improve statistical performance but may damage efficiency. Corre- spondingly, smaller capacities permit fewer memories to be scored for a given query, which may improve computational efficiency by sacrificing predictive performance.
We check whether a leaf node is at capacity each time memory is added to it (i.e., |n.M] 2 c)- If is, the leaf is split, turning n into an internal node. The splitting process begins by assigning routing behavior to the node, which governs how new samples will traverse the tree. This is done by (1) approximating the first principal component of its stored memories and (2) computing the median value of memories projected onto this vector. When new sample arrives, project it onto this eigenvector and route the sample left if the corresponding value is less than or equal to this median and otherwise route it right (see Line 3 in Algorithm 3
We follow the same rule for distributing memories across the children of a newly split node memories with projection less than or equal to this median are stored in the left child
4

---

Under review as a conference paper at ICLR 2023
Algorithm 3 Leaf Functions
function SPLITLEAF(:: Node)
n.router <TPPEIGGN
n.boundary <- median( (n.router, Im (1m, Dmm) E n.MM))
n. <- {(rm Dm) E n.M (n.router, Fm/ S .n.uouddar))
n.right.M f {Zm, ym) E n.M (n.router, Fm) > n.boundary]
n.M t- 0
end function
function TOPEIGEN(M C R2d IR)
X {Im (Imm ym E M
D X E dMd
X X (4|ar |M (
Mean center the rows of X
random unit vector in RIMI
for n < 1 to M do
((X..
V 10+ (X,,, wll
end for return v end function
and others are stored in the right. The approximate cigenvector assigned to n.router is computed us- ing Oja's method, popular approach for performing PCA on streaming data (Balsubramaní al., 2013) as shown in Algorithm [ Because the decision boundary n. n.boundary is the median of the pro- jected memories, the allocation of data across children in a newly split node is nearly even; hopefully resulting in well-balanced tree, A plot of 4, 000 memories within a tree can be seen in Figure
3 RELATED WORK
This section overviews alternative memory structures through the lens of our desiderata: self- consistency, incremental growth, learning, and sub-linear computational complexity. Two illuminat- ing extreme points are associative data structures (e.g., hashmaps) that do not learn and only support exact retrieval; and supervised models (e.g., ordinary least squares) which compile experience into structure which supports fast retrieval, but cannot guarantee self-consistency.
Classic nearest-neighhor models (Friedman et al. 1975) are self-consistent and grow incrementally. but do not learn (the metric) and have poor computational complexity; considerable attention has unsurprisingly been put towards improving nearest neighbors algorithms along these axes. Exact or approximate neigest-neighbor methods, e.g., [Beygelzimer et al. (2006); Ram & Sinha (2019): Datar al. (2044); Dasgupta & Sinha (2013), can reduce computational complexity but (beyond inserting new memories) do not learn. Weinberger al. (2005) learn metric for use with nearest-neighhors but does not learn incrementally. Analogously, learned hash functions (Salakhutdinov & Hinton
2009 Rastegari al. 2012) produce an associative data structure but learning is not incremental.
Diffcrentiable neural memory systems learn an associative mapping using gradient- gradient-based optimiza- tion (Sukhbaatar et 2015
Graves et al.) (016)). Unfortunately their computational demands are severe, preventing practical applications with large memories and prompting variants that use cus-
tom hardware (Ni et al. 2019
Ranjan et al. 2019) or exploit sparsity (Karunaratne et al. 2021).
The only memory model in the literature possessing all of EMT's ' desiderata is the contextual mem- ory tree (CMT) (Sun al., 2019). EMT and CMT both use an internal tree structure with routers and global scorer. EMT differs from CMT in three ways (1) EMT uses fixed top-egeinvector routers while CMT learns routers incrementally, (2) the EMT scorer uses pairwise feature differences rather than CMT's feature interactions (the importance of this can be seen in our ablation studies be- low) and (3) the EMT scorer is updated with respect to a ranking loss function rather than CMT's squared loss. As discussed later, (1) and (2) together ensure strong self-consistency constraint, such that exact memories are returned available. Because CMT updates routing mechanisms, exact matches for particular observation may be inaccessible.
Finally, it remains an open question how to best use episodic memory. For example, the work of (Lengyel & Dayan, 2007] evaluates directly using memories decide how to act in sequential
5

---

Under review as a conference paper at ICLR 2023
Reward Difference
With Self ColiisoCnst Is Best (180)
0.3
Tie (20)
Without Self-Consistency Best (6)
Reward
0.2
0.5
0.1
With Self-Consistency
0.4
Without Self-Consistency
0.0
51
102
153
206
1000
2000
3000
4000
Dataset
Interaction
Figure 3: A per-dataset comparison final progres- sive reward between EMT-CB and a variant of EMT- CB without self ceff-consistency. Each point is single dataset. The y-axis shows the difference between the learners. The x-axis is ordered by this difference.
Figure Progressive reward for EMT-CB and a variant of EMT-CB without coniisonsis. Each line is an average over 206 datasets in the OpenML repository. Progressive reward is shown as function of interactions and vertical lines are standard error.
environment. Other work has used episodic memory tool to support supervised learner either as input into a non- non-parametric model (Blundell et al., 2016 Pritzel et al., 2017) or as a tool to train supervised learner (Lin et al. 2018). Still more has treated episodic memory supervised learning and the goal is to combine the two model's predictions Hansen et al. (2018); Feng et al. (2017). Our work evaluates EMT in terms of its performance as direct predictor (EMT- CB) and as complementary predictor to a parametric model (PEMT-CB).
complement to
EXPERIMENTS
The experiments in this section consider the Contextual Bandit (CB) framework, setting in which an agent is sequentially presented with a d-dimensional "context" vector 2, and is required to execute one of |A] actions. For each executed action a, A. the agent receives corresponding reward ye- The goal of the agent is to maximize the total reward received over the course of an evaluation.
The EMT algorithm presented above is a general-purpose supervised learning algorithm, and not an algorithm for solving CB problems specifically. We however can easily adapt EMT for the CB setting by augmenting it with an exploration algorithm (see Algorithm 4.. For our experiments we used an e-greedy exploration algorithm with .1. That is, on each iteration with probability an action in A was selected with uniform random probability. Otherwise for each a A EMT is queried and the action with the highest predicted reward is taken. We will call this adaptation EMT-CB. Code to reproduce all results is available at redacted.
Datasets We consider 206 contextual bandit problems derived from OpenML (Vanschoren al. 2014) classification datasets via supervised-tor -o-baddit transformation (Bietti et al. (021). OpenML data are released under a CC-BY license. For large datasets, we consider random subset of 4, 000 training examples. We also scale the i-th feature of every sample -; in each dataset by (/mxx mimm a!). For each problem, the action set A the set of classification labels. When an agent correctly classifies example reward of one is given otherwise a reward of zero is given.
Evaluation Learners are evaluated online via progressive loss (Blum et al. 1999). Specifically, each time the agent receives reward, we update the total reward earned, normalized by the total number of interactions. After T total interactions, the progressive reward is 1/r Σ Vt- These pro- gressive rewards plotted throughout the course of this section. Additionally, in order to calculate confidence bounds every data set is evaluated 50 times with a different random seed for each.
4.1
SELF-CONSISTENCY
The EMT incorporates two particular design decisions: (1) using eigenvector routing and (2) using scorer where self-consistency is hard constraint, which mentioned earlier, guarantees that an exact-match memory is always retrieved as long as one is available.
To examine the importance of self-consistency, we compare EMT variant that does not include this property. In this variant, we modify Line of Algorithm such that the input to the regressor,

---

Under review as a conference paper at ICLR 2023
Reward Difference
EMT-CB is Best (44)
0.2
Tie (11)
0.6
Parametric Is Best (151)
0.0
0.5
0.4
Parametric + EMT-CB + CMT-CB
0.2
1000
2000
3000
4000
102
153
206
Interaction
Dataset
Figure 5: A progressive reward comparison be- tween EMT-CB and parametric, where each line corresponds to an average over 168 datasets in the OpenML. repository. Reward shown as function of the number of environment interactions and ver- tical lines denote standard error. Parametric actually outperforms EMT on average, which we address with the hybridized algorithm discussed in Section
Figure 6: A per-dataset comparison of final progres- reward between EMT-CB and parametrie. Each point corresponds to a single dataset, axis shows the difference between the two learners. The horizontal axis is ordered by this performance difference. Here datasets for which parametric does better, there are 44 datasets where EMT is higher performing.
the vertical
that while there many
Algorithm Contextual Bandit EMT (EMT-CB)
Initialize: c and e as desired
function PREDICT(2: E (R
With probability return uniform random a E A Otherwise return arg maxaeA EMT.Query((Ze,, a) end function
function LEARN(I, Rd, a, E Yt R)
EMT. CMTT.Learn((r.) 0z). y1)
end function
is the interaction of features in samples 21 and T2, instead of dimension-we -ise difference. As consequence, is not the case that (w. 2) guaranteed be zero for identical samples.
dataset-by-datee dataset basis. The plotted points show the difference total progressive reward averaged over random seeds. The plot shows that in 180 of the 206 datasets considered, self-consistency provides significant improvements. In the 6 where it does not, the performance diffcrence is negligible.
Figure B compares the performance of these algorithms
Figure 4 compares the average progressive reward for these two algorithms over 168 datasets, with respect to the number training examples. The number of datasets is slightly smaller here because omit datasets with fewer than 000 training examples. We that the self-consistent version has significantly better performance over all interactions on average.
4.2 COMPARISON TO ALTERNATIVE EPISODIC MEMORY DATA STRUCTURES
The most natural comparison EMT is, as mentioned earlier, Contextual Memory Trees. The CMT implementation used throughout this work for CMT-CB is the official Vowpal Wabbit (VW) (Lang- ford et al. 2007) implementation published by [Sun al. (201)). It is also worth noting that the original CMT paper evaluated the performance of CMT in an online framework with full-feedback, meaning that the agent receives information about the correct answer for each 2; it encounters. the partial-feedback scenarios studied here, where the agent only receives information corresponding to the executed action, we find CMT is far less performant overall.
Specifically, results demonstrate that EMT's differences in routing and scoring endow it with performance superior to CMT in bandit scenarios. We see this both in terms of performance over time (Figure (5) and total performance individual datasets TTable[aadd Appendix Figure where EMT soundly outperforms CMT. This plot also compares to a parametric algorithm discussed the proceeding section.

---

Under review as a conference paper at ICLR 2023
0.3
per-dataset comparison of final progressive reward between PEMT- CB and parametric. Each point corre- sponds to single dataset, and the vertical axis shows the difference between the two learners. The horizontal axis ordered by this performance difference. PEMT-CB almost always performs at least as well as the parametric approach.
Figure 7:
Reward Difference
PEMT-CB Best (110)
Tie (88)
0.2
Parametric Is Best (8)
0.1
0.0
0
51
102 Dataset
153
206
4.3
COMPARISON TO PARAMETRIC MODEL
Another natural comparison for this analysis is between EMT-CB and parametric CB learner. A parametric approach could be thought of as encoding semantic memories, focusing on high-level concepts rather than specific experiences.
The parametric model is a linear regressor, taking context-action features as inputs and predicting expected rewards. The model is trained using SGD on the squared loss, implemented by VW. Like EMT-CB and CMT-CB, this model is e-greedy, selecting uniform random actions with probability and selecting the action that yields the highest predicted reward with probability 1-c. We use VW's default hyperparameter values (including
.1) along with 1st and 2nd-order polynomial features. Table and Figure (6 shows that EMT beats the parametric model on 44 cases (a minority).
The results here are reminiscent of the "no free lunch" theorem (Wolpert & Macready 1997) which states there is no one universal learner that wins in all problems. Rather we must try and determine the most appropriate learner for each circumstance. The following subsection proposes a simple and high- ser-peerformnn method that is able to combine parametric and EMT-CB with almost no downsides.
To understand the dataset qualities that result in EMT-CB outperforming the parametric approach, we conducted a thorough meta-analysis, which provided Appendix 6 We find that the qualities most predictive of whether EMT will outperform parametric are (1) the mutual information between samples and labels and (2) how well the top cigenvector explains dataset variance. Intuitively, the sample with the data stored its corresponding leaf and the latter could be thought as how reasonable is for EMT to aggregate leaf samples based on the first principle component.
former could be thought of how reasonable is compare
4.4 COMPARISON STACKED TO PARAMETRIC
Due to the mixed results of EMT-CB when compared against the parametric algorithm, we propose simple method to combine the two learners, which we call PEMT-CB (and PCMT-CB when applying this method to CMT-CB). This combination is a simple stacking approach (Wolperi) 1992] where the rewards for each action predicted by EMT-CB are passed to the parametric CB model as a single additional feature. The parametric learner has idea the additional feature came from EMT-CB and treats it simply as an additional parameter to optimize via SGD.
Figure 7 shows that PEMT-CB is able to outperform the parametric model on 110 individual datasets and under-performs by a very small margin in only 8 datasets. It is worth noting that stacking two learners in partial feedback setting is more challenging than in full-feedback setting because both learners may have different data needs for learning and not all actions can be explored. Previous work has sought explicitly address this challenge from statistical perspective (Agarwal al., 2017), but here we find the simple stacking approach to be surprisingly powerful.
4.5 BOUNDED MEMORY ANALYSIS
For our final analysis we examine how sensitive EMT is to a memory budget, limiting the amount of memories EMT is permitted to keep. In order to maintain this limit we use a simple least-recently- used (LRU) strategy to eject a memory whenever our memory budget is exceeded. To get a sense of how the loss of memories might impact performance time filter datasets down to the 116 which have 32, 000 or more training examples and evaluate out to 32, 000 iterations rather than the 4, 000 explored up to this point.
8

---

Under review as a conference paper at ICLR 2023
Figure 8: The performance loss between the unbounded PEMT-CB and bounded PEMT-CB algorithms is minimal even with a 3. 1% memory budget. Addition- ally, at no budget level does PEMT-CB performance drop below the parametrie model. Each line corresponds to an av- erage over 116 datasets in the OpenML repository. Reward is function of the number of environment inter-actions and vertical lines denote standard error.
0.7
Reward
0.6
0.5
1,000
16,000
67725
32,000
Parametric
0.4
33250
31123
8000
16000
24000
32000
Interaction
We find that even with budget of 1, 000 memories (with memory eviction via LRU) PEMT-CB still outperformed parametric alone with statistical significance on 61 datasets (see Appendix Figure [4 for a per-dataset comparison). Figure 8 shows that a 16, 000-sample memory budget works almost exactly as well the no-budget version of PEMTT-B. That is, equivalent performance tained despite the fact that the memory can only hold half as much information. Even when using an extremely conservative memory budget of 1, 000 samples, PEMT-CB only accrues loss in reward of .0075 on average. Overall, very few memories are needed to consistently beat the parametric approach in isolation, and not much is needed match the performance of the unbounded memory variant of PEMT-CB.
be at-
DISCUSSION AND FUTURE DIRECTIONS
Summary As discussed in Section 3 finding methods that effectively use episodic memory is an important and active area of research. This work proposes new episodic memory model for sequential learning called Figen Memory Trees (EMT). EMT possesses four distinguishing charac- teristies: (1) self-consistency. (2) incremental growth, (3) incremental learning, and (4) sub-linear computational complexity. EMT adds to an important but somewhat understudied area in online learning: efficient, online memory models.
To evaluate the effectiveness of EMT we converted 206 datasets from OpenML into contextual bandit problems. Using these we compared EMT's performance to an alternative online memory model, CMT, and parametric CB learner. EMT outperformed CMT across the board (see Figure while outperforming parametric 44 of the 206 (see Figure (6) datasets.
We further proposed PEMT-CB, a simple extension of EMT that is able to consistently outperform both EMT and parametric alone, even when forced to use a small memory budget (see Table []. The aggregate strategy passes EMT reward predictions as a feature into the parametric learner. This result is important for a number of reasons. First, is suggests that EMT offers a no-downside method for improving existing CB algorithms. Second, to our knowledge, this is the first work demonstrating that stacking can improve performance in the partial feedback setting of contextual bandits (cf. (Agarwal et al. 2017)).
Applied machine learning models often have to work with resources constrained by business and operational requirements. For memory models this is often the amount of memories that can be stored and efficiently accessed. We evaluated PEMT-CB performance for four memory budgets, showing that observed performance improvements of PEMT-CB an extremely constrained memory capacity (see Figure 8). Perhaps most importantly, constraining the memory budget had no negative impact on the performance of the parametric learner.
largely maintained even with
Applications, limitations and future studies The fast reactivity memorization, when appropri- ate, is appealing in real world applications where data acquisition incurs natural costs via acting in the world. Thus, incorporating memorization practice can broaden the applicability of contextual bandits, c.g., to scenarios in information retrieval and dialogue systems (Bouneffouf al. 2020).
EMT also seems especially well suited for quick-changing environments. Rather than requiring multiple SGD steps to update, new memories are immediately accessible after insertion, and stale memories can be directly removed or added when situations change in known ways. This highlights both a limitation of this study as well The fixed nature of EMT's top-eigen routers along with our simple LRU eviction rule for memory budgeting likely make the model susceptible to performance degradation when environments shift.
opportunity: how robust is EMT to non-stationarity?

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We have taken considerable measures to ensure results are as reproducible as possible. We chose to large number of publicly available datasets with many replications. We have also provided our algorithm code, experiment code, result data, and plotting code in the supplement. The experiment code provided, when executed, will download all appropriate datasets, apply all data transfor- mations described in the paper, and create 50 shuffled replicates for each data set using the same random seeds used by the authors. Finally, our supplementary code also includes conda environ- ment file to help future researchers recreate our development environment on their machines when running the experiments.
REFERENCES
Sarah Daniel Abdelmessih, Faisal Shafait, Matthias Reif, and Markus Goldstein. Landmarking for meta-learning using rapidminer. In RapidMiner community meeting and conference. Citeseer, 2010.
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire, Corralling band of bandit algorithms. In Conference on Learning Theory, pp. 12-38. PMLR, 2017.
Akshay Balsubramani, Sanjoy Dasgupta, and Yoav Freund. The fast convergence of incre- mental pea. C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Wein- berger (eds.), Advances in Neural Information Processing Systems, volume 26. Curran Asso- ciates, Inc., 2013. URL /ttp///tps//prrreeeinoo.... wew.eeeeedddnnn.e.e.e...e...e..e http://g.....aoooooocpcpp/////// pctpc///ppaprr/1///flee .pdf
Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Pro- ceedings of the 23rd international conference on Machine learning, pp. 97-104, 2006.
Alberto Bietti, Alekh Agarwal, and John Langford. A contextual bandit bake-off. Journal of Ma- chine Learning Research, 22(133):1-444 49, 2021.
Avrim Blum, Adam Kalai, and John Langford. Beating the hold-out: Bounds for k-fold and progres- sive cross-validation. In Proceedings of the twelfth annual conference on Computational learning theory, pp. 203-208, 1999.
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Z Leibo, Jack Rae, Daan Wierstra, and Demis Hassabis. Model-free episodic control, 2016.
Djallel Bouneffouf, Irina Rish, and Charu Aggarwal. Survey on applications of multi-armed and contextual bandits. In 2020 IEEE Congress on Evolutionary Computation (CEC), pp. 1-8, 2020. doi: 10.1E099CC44 202.499600000000977777833
Ciro Castiello, Giovanna Castellano, and Anna Maria Fanelli. Meta-data: Characterization of input features for meta-learning. In International Conference on Modeling Decisions for Artificial Intelligence, pp. 457-468. Springer, 2005.
Sanjoy Dasgupta and Kaushik Sinha. Randomized partition trees for exact nearest neighbor search. In Conference on learning theory, pp. 317-337. PMLR, 2013.
Mayur Datar, Nicole Immorlica. Piotr Indyk, and Vahab Mirrokni. Locality-sensinee hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry, pp. 253-262, 2004.
Yang Feng, Shiyue Zhang, Andi Zhang, Dong Wang, and Andrew Abel. Memory-augmented neural machine translation. arXiv preprint 17X.v:1708... 100.0000,,,0005,, 2017.
Jerome Friedman, Forest Baskett, and Leonard Shustek. An algorithm for finding nearest neigh- bors. IEEE Transactions on computers, 100010):100001000 1975.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwinska, Sergio Gómez Colmenarejo, Edward Grefenstette. Tiago Ramalho, John Agapiou, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538
(7626):471-476, 2016.
10

---

Under review as a conference paper at ICLR 2023
Steven Hansen, Alexander Pritzel, Pablo Sprechmann, Andre Barreto, and Charles Blun- dell. Fast deep reinforcement learning using online adjustments from the past. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018. URL
www.ingn....iinieeeeeeeeee wwwrieuurp.... wtt..eepp....pppre////////. pcs.ccc//pperr201///1ee Paper. pdf
Steven CH Hoi, Doyen Sahoo, Jing Lu, and Peilin Zhao. Online learning: A comprehensive survey. Neurocomputing, 459:249-289, 2021.
Geethan Karunaratne, Manuel Schmuck, Manuel Le Gallo, Giovanni Cherubini, Luca Benini, Abu Scbastian, and Abbas Rahimi. Robust high-dimensional memory-augmentedd neural networks. Nature communications, 12(1):1-12, 2021.
John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
John Langford, Lihong Li, and Alex Strehl. Vowpal wabbit online learning project, 2007.
Máté Lengyel and Peter Dayan. Hippocampal contributions to control: The third way. In Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Newral Information Processing Systems, volume 20. Curran Associates, Inc., 2007. URL https: http:////occeddiec ngs neur iis..rpp.... cc/ paper/
Paper...d
Zichuan Lin, Tianqi Zhao, Guangwen Yang, and Lintao Zhang. Episodic memory deep q-networks. In Proceedings of the Twenty-Seenthh International Joint Conference on Artificial Intelligence, IJCAI-18, pp. 2433-2439. International Joint Conferences on Artificial Intelligence Organiza- tion, 7 2018. doi: 10. 2224963//jcai.22188333 UR//atpp.//oo...rr//022222////// 2018/337
Ana C Lorena, Luís PF Garcia, Jens Lehmann, Marcilio CP Souto, and Tin Kam Ho. How complex is your classification problem? survey on measuring classification complexity. ACM Computing Surveys (CSUR), 52(5):1-34, 2019.
Viktor Losing, Barbara Hammer, and Heiko Wersing. Incremental on-line learningg A review and comparison of state of the art algorithms. Neurocomputing, 275:1261 1274, 2018.
Kai Ni, Xunzhao Yin, Ann Franchesca Laguna, Siddharth Joshi, Stefan Dünkel, Martin Trentzsch, Johannes Müller, Sven Beyer, Michael Niemier, Xiaobo Sharon Hu, et al. Ferroelectric ternary content-addressablee memory for one-shot learning. Nature Electronics, 2(11):521-525 2019.
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adrià Puigdomènech Badia, Oriol Vinyals, Demis Hassabis, Daan Wierstra, and Charles Blundell. Neural episodic control. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learn- ing, volume 70 of Proceedings of Machine Learning Research, pp. wwt.:asss.m.........e.. ptt.pppe////7///ppptaaa11117
PMLR, 06-11
Aug 2017. URL httphttt/ps.ccceeeeeeee
Parikshit Ram and Kaushik Sinha. Revisiting kd-tree for nearest neighbor search. In Proceedings of the 25th acm sigkdd international conference on knowledge discovery & data mining. pp. 1378- 1388, 2019.
Ashish Ranjan, Shubham Jain, Jacob Stevens, Dipankar Das, Bharat Kaul, and Anand Raghu- nathan. X-mann: A crossbar based architecture for memory augmented neural networks. In Proceedings of the 56th Annual Design Automation Conference 2019, pp. 1-6. 2019.
Mohammad Rastegari, Ali Farhadi, and David Forsyth. Attribute discovery via predictable dis- criminative binary codes. In European Conference on Computer Vision, pp. 876-889. Springer, 2012.
Matthias Reif, Faisal Shafait, Markus Goldstein, Thomas Breuel, and Andreas Dengel. Automatic classifier selection for non-experts. Pattern Analysis and Applications, 17(1):83 2014.

---

Under review as a conference paper at ICLR 2023
Ruslan Salakhutdinov and Geoffre Hinton. Semantic hashing. International Journal of Approxi- mate Reasoning, 50(7):969 97889999777770 2009.
Sainbayar Sukhbaatar, Jason Weston, Rob Fergus, et al. End-to-end memory networks. Advances in neural information processing systems, 28, 2015.
Wen Sun, Alina Beygelzimer, Hal Daumé Iii, John Langford, and Paul Mineiro. Contextual mem- ory trees. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 6026-6035, PMLR, 09-15 Jun 2019.
Endel Tulving. Episodic and semantic memory. In Endel Tulving and Wayne Donaldson (eds.), Organization of memory, pp. 381-402. Academic Press, Oxford, England, 1972.
Joaquin Vanschoren, Jan N Van Rijn, Bernd Bischl, and Luis Torgo Openml: networked science in machine learning. ACM SIGKDD Explorations Newsletter, 15(2):49-66 2014.
Kilian Q Weinberger, John Blitzer, and Lawrence Saul. Distance metric learning for large margin nearest neighbor classification. Advances in neural information processing systems, 18, 2005.
David H Wolpert. Stacked generalization. Neural networks, 5(2):241-259) 1992.
David H Wolpert and William G Macready. No free lunch theorems for optimization. IEEE trans- actions on evolutionary computation, 1(1):67-22, 1997.
Guangxiang Zhu, Zichuan Lin, Guangwen Yang, and Chongjie Zhang. Episodic reinforcement learning with associative memory. In International Conference on Learning Representations, 2020. URL Stlpttts: /ttp:::////eeeeeeee/e net/ forum? d=Hkx joxBYDB
12

---

Under review as a conference paper at ICLR 2023
Appendix
6 META-DATA ANALYSIS
An analysis was performed understand the characteristics of the datasets where EMT-CB outper- formed the parametric CB learner. Twelve dataset features were selected from the meta-learning literature. These twelve features are described in Table 2
We trained a random forest (RF) model using the features in Table 2 to predict when EMT would outperform the parametric learner. This model was able predict winning CB model with macro
Table 2: The features used to analyze why EMT outperformed the parametric learner on some datasets.
Feature
Reference
Description
Top Eigenvector Explained
The percentage of dataset variance explained by the top eigenvector.
Eigenvector Count To Ex- plain 95% Var
Lorena al. (2019)
The number of eigenvectors required to explain 95% of the feature variance.
Mean Mutual Information Feature/Label
Castiello
et
al.
The average amount of mutual information between each feature and the target label.
2005
Reif et al.
2014
Nearest Neighbor Accu- racy
Reif et al. (2014);
The accuracy of 1 nearest neighbors classifier on the dataset.
Abdelmessih ct al. (2010)
Single Node Decision Tree Accuracy
Reif et al. (2014);
The accuracy a single node decision tree the dataset.
Abdelmessih et al. 2010
Naive Bayes Accuracy
Reif al. (2014);
The accuracy of naive Bayes classifier on the dataset.
Abdelmessih et al. (010
Normed Label Entropy
Lorena et al. (2019); Castiello
The amount of entropy in the class distribution (normed so that 1 is maxi- mum entropy).
et al.
2005 : Reif et al.
2014
Noise to Signal Ratio
Casteello al. (005
Ratio extra feature entropy to mutual information be- tween features and labels. The count of the number of binary features in the dataset. For one hot en- coded categorical features this counts every level.
Binary Feature Count
Percent of Nonzero Features Lorena
2019
The percentage of non-zero features in the dataset.
Efficiency of Best Single Lorena et Feature
2019
measure of the single best feature's ability to distin- guish classes. The efficiency averaged across all one-v- one label matchups.
Maximum Fisher's Discrim- inant Ratio
Lorena al. (019
A Measure of feature over- lap when discriminating class labels. The ratio is av- eraged across all one-v-one label match-ups.
13

---

Under review as a conference paper at ICLR 2023
Reward Difference
Percent Variance Explained the Eigenvector
60%
0.2
40%
20%
Dataset
Figure 9: This plot visualizes the relationship between the variance explained by the top-eigenvector for a dataset and the performance of EMT-CB versus parametric. The x-axis represents our study datasets. The blue line shows the difference in performance between EMT-CB and parametric. The yellow points show the feature values for cach datasct and the yellow line show the rolling average all the yellow points.
Reward Difference
100%
Percent of Nonzero Features
80%
60%
40%
20%
Dataset
Figure This plot visualizes the relationship between the percent of nonzero features in a dataset and and the performance EMT-CB versus parametric, The x-axis represents our study datasets. The blue line shows the difference in performance between EMT-CB and parametric. The yellow points show the feature values for each dataset and the yellow line show the rolling average of all the yellow points.
Reward Difference
Average Number of Bits of Mutual Information Between Features and Class Label
0.2
0.3
0.0
0.2
-0.2
-0.4
0.0
Dataset
Figure 11: This plot visualizes the relationship between the mutual information metadata feature and the performance EMT-CB vs parametric. The x-axis represents our study datasets. The blue line shows the difference in performance between EMT-CB and parametric. The yellow points show the fcature values for each dataset and the yellow line show the rolling average of all the yellow points.
fl score of .22 on held-out datasets. Figure shows the average reduction in Gini impurity for each feature.
We then trained compact RF model the minimum features needed. We used repeated k-fold cross validation with feature selection applied to the training split before fitting our RF model. The final reduced model had f'l score of .79 on held out data using only features; percent of variance explained by the top cigenvector, percent of nonzero features, average amount of mutual information between features and labels (measured in bits). We now look these more closely.
The first of these features measures the explanatory power of the top eigenvector. We can see that this has a positive correlation with the performance of memory in Figure [ We believe these datasets with more informative top eigenvector for the whole dataset likely have more informative top eigenvector routers leading to improved tree searches for the EMT.
The second of these features is the percentage of non-zero values in a dataset. For this feature we observed that the fewer non-zero features in a dataset the better EMT performed (see Figure I0). When we looked at datasets with a high percentage of zero values the most common cause were large amounts of one hot encoded categorical features. Categorical variables with large number of levels naturally difficult to compare via metric since each level is equidistant from every other level. this case learning an effective scorer would become very challenging parametric would have greater chance of beating FMTT-CB.
14

---

Under review as a conference paper at ICLR 2023
Gini Impurity Reduction
0.15
0.10
0.05
0.00
Eigenvedor Count To Explain 95% Var
Top Eigenvector Explained
Noise to Signal Ratlo
Mean Mutuaa Information FeaturefLabll
Naive Bayes Accuracy
Efficiency Best Single Feature
Maxmmmm Fisher's Discriminant Ratio
Percent of Nonzero Features
Binary Feature Count
Single Node Decision Tree Aspuracy
Normad Label Entrapy
Nearest Neightor Accuracy
Figure 12: The average decrease impurity in RF model predicting whether EMT outperforms parametrie.
The final feature in our compact model was the mutual information between individual features and a dataset's class (see Figure II]. This is a non-normalized value so datasets with more labels and fewer non-zero features will likely have higher values of this feature. For example, a dataset with binary label has an upper limit of for this feature while a dataset with 30 class labels has upper limit of 4.91. High values this variable also indicate that there is strong statistical relationship between features and class labels but place no restriction on the functional that relationship may take.
SUPPLEMENTARY FIGURES
Reward Difference
EMT-CB Is Best (177)
0.2
Tie (18)
CMT-CB is Best (11)
0.1
0.0
51
102 Dataset
153
206
Figure 13: A per-dataset comparison of final progressive reward. Each point corresponds to single dataset. The y-axis shows the difference between the two learners. The x-axis is ordered by this performance difference.
Reward Difference
0.100
Parametric Best
Reward Difference
0.100
Parametric Is Best (4)
0.075
0.075
Tie (52)
PEMT-CB 32k Memories Best (80)
PEMT-CB 1k Memories Best (61)
0.025
0.025
0.000
0.000
30
60
90
116
30
60
90
116
Dataset
Figure per-dataset comparison of final progressive reward between memory budgeted PEMT-CB and parametric. The left plot shows this difference when there no bounding. The right plot shows the difference when bounding to IK memories. Each point corresponds to single dataset. The a-axis shows the difference between the two leamners. The x-axis is ordered by this performance difference.
15


Reviews:
[{"review_id": "K31_oUpEcT", "reviewer": "Reviewer_ibPD", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes Eigen Memory Tree to serve as an efficient data structure for online memory. ", "summary_of_the_review": "I don't think ICLR is the right venue for this paper.\n", "strength_and_weaknesses": "Pros: potentially useful.\n\nCons: I am not convinced ICLR is the right place for this paper. While there is connection to machine learning, the key contribution of a more efficient and practical data structure should be evaluated by community who focus on such issues. I believe database would be a better venue. It is hard to evaluate such work in the context of ICLR without comparing to other similar data structures.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "C_B1AwQ_RdQ", "reviewer": "Reviewer_UauN", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work introduces a new data structure based on a binary tree. Each node is split using PCA on the node data. With respect to existing data structure EMT are easier to learn in streaming tasks. The most similar work to EMT are CMT which have similar structure internally and pretty identical mechanism to route and score data. EMT differ in term of self-consistency guaranteeing such property. \n\nExperiments are performed on bandits as a use case for streaming tasks requiring a memory structure.\n\nEMT alone is not really competitive with respect to other mechanism on bandit problems, but the parametric variant is able to outperform many existing memory structures on most of the 206 tasks taken into consideration.\n\n", "summary_of_the_review": "The paper is clearly explained and the method has some interesting properties, unfortunately to outperform the competition the structure must be stacked with an existing parametric approach. Moreover the approach is also very close to CMT. Some other data structures, e.g. the plethora of indices in FAISS could be taken into consideration when performing the experiments.", "strength_and_weaknesses": "Strengths\n- The analysis of memory properties is well executed and the algorithm motivation is clear\n- Code is provided for full reproducibility\n\nWeaknesses\n- Method is very close to CMT\n- The comparison is kind of limited given that modern libraries such as FAISS could be used for example", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-qWwX2YeQy", "reviewer": "Reviewer_RGJi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes a novel episodic memory model for sequential learning, termed an Eigen Memory Tree (EMT). EMT adds to an important but under-studied topic in online learning: efficient online memory models. To evaluate the effectiveness of EMT, the authors tested 206 datasets from OpenML and compared with another online memory model, CMT, and a parametric CB learner. EMT outperforms CMT across the board, while outperforming parameters in 44 out of 206 datasets.", "summary_of_the_review": "See Strength & Weaknesses", "strength_and_weaknesses": "Overall, the paper is well-written and easy to follow. The experimental results demonstrate that the proposed method is promising. The authors use fixed top-eigenvector routers, pairwise feature differences, and a loss function according to ranking in EMT, enabling CMT improvement.\n\nIn Section 4.5, even with an extremely conservative memory budget of 1,000 samples, PEMTCB only incurs a reward loss of 0.0075 on average. Very little memory can beat parametric methods in isolation. Is this conclusion related to the data set? If you can try the performance on these data sets~ (AmazonCat, Wiki10, Amazon [1]), the conclusion will be more convincing.\n\nA typo:\n1. “eThe EMT incorporates two particular design decisions”\n\n[1]. Jasinska-Kobus, Kalina, et al. \"Online probabilistic label trees.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject