We propose our novel episodic memory, Levelled Graph Episodic Memory method (LeGEM), via the levelled graph data structure. LeGEM memorizes each agent's past trajectories which are partial observations and the unilateral action of the agent. During training, each agent \(i\)  collects its individual trajectories \(\tau _{i}\) . We then define \(\tau _{i}\)  of agent \(i\)  as \( \tau _{i}=[(o^{0}_{i},\mathbf {\tilde{\text{$u$}}}^{0}_{i}, r^{0}), \cdots , (o^{T-1}_{i},\mathbf {\tilde{\text{$u$}}}^{T-1}_{i}, r^{T-1})]\) ,
where \(T\)  is the length of the trajectory and the triplet \((o^{t}_{i},\mathbf {\tilde{\text{$u$}}}^{t}_{i}, r^{t})\)  represents the observation, action and reward of timestep \(t\) . Note that \(r^{t}\)  is globally shared between agents. We define agent \(i\) 's LeGEM as a directed graph \(\phi ^{t}_{i} \in \Phi _{i}\)  where \(\Phi _i\)  is the set of graphs of agent \(i\)  and \(\phi ^{t}_{i}\)  is the \(t\) -th graph of \(\Phi _{i}\) , \(t \in \lbrace 0, \cdots , T-1\rbrace \) . Each \(\phi ^{t}_{i}\)  consists of a tuple of \(\left( \Psi , \Xi \right)\)  where \(\Psi \)  is the set of nodes and \(\Xi \)  represents the set of edges that connect nodes in the graph.
To model an agent's behaviour explicitly and make the trajectories
of agents easy to represent,
we create \(T\) 
graphs for each agent and let
\(\Phi _i=\lbrace \phi ^{t}_i\rbrace ^{T-1}_{t=0}\)  where \(T\)  is the maximum level of all graphs and the maximum length of the episode as well. The maximum level of \(\phi ^{t}_i\)  is \(t+1\) . The node contains key, visit count and pointers connecting the precursors (node at the previous level) and the successors (node at the next level).
Besides the \(\phi ^{t}_{i}\) , we define the sub-graph set of \(\phi ^{t}_{i}\)  as \(\Phi ^{t,\Omega }_{i}=\lbrace \phi ^{t,\omega }_{i}\rbrace ^{\Omega -1}_{\omega =0}\)  by using the discretized episode return and there are \(\Omega \)  sub-graphs. \(\phi ^{t,\omega }_{i}\)  is the \(\omega \) -th sub-graph whose episode return is \(\Upsilon \texttt {[} \omega \texttt {]}\)  (\(\omega \in \lbrace 0, \cdots , \Omega -1\rbrace , \Upsilon =[0, \cdots , r^{t,i}]\) ) where \(r^{t,i}\)  is the discretized maximum episode return of \(\phi ^{t}_{i}\) .
Unlike many parameterized episodic memory using state/observation as the key [1]}, [2]},
we resort to afterstate [3]}. That is, we use agent \(i\) 's observation \(o^{t}_{i}\)  and action at timestep \(t\) , \(\mathbf {\tilde{\text{$u$}}}^{t}_{i}\) , to define the key \((o^{t}_{i}, \mathbf {\tilde{\text{$u$}}}^{t}_{i})\) . We provide an example to showcase the relationship between sub-graph and the graph in Fig. REF . For complex and continuous state scenarios, for example StarCraft II scenarios, we use SimHash [4]} to discretize the key \((o^{t}_{i}, \mathbf {\tilde{\text{$u$}}}^{t}_{i})\) .
This technique has been widely used in commercial search engines and RL [5]}. Visit count indicates the total visits made by agent \(i\)  to the node. It initial value is 1. Note that nodes are bidirectional since it is helpful for searching (see Sec. REF ).
