Artifacts as Memory Beyond the Agent Boundary
Type: kb/sources/types/snapshot.md
Author: John D. Martin; Fraser Mince; Esra'a Saleh; Amy Pajak Source: https://arxiv.org/abs/2604.08756 Date: 2026-04-09
Cover Page
Artifacts as Memory Beyond the Agent Boundary
John D. Martin1,2,† , Fraser Mince3,† , Esra’a Saleh3,4,5 , Amy Pajak3,6
Keywords: Memory, Artifacts, Situated Cognition, Bounded Agent
Summary
The situated view of cognition holds that intelligent behavior depends not only on internal
memory, but on an agent’s active use of environmental resources. Here, we begin formaliz-
ing this intuition within Reinforcement Learning (RL). We introduce a mathematical framing
for how the environment can functionally serve as an agent’s memory, and prove that certain
arXiv:2604.08756v1 [cs.AI] 9 Apr 2026
observations, which we call artifacts, can reduce the information needed to represent history.
We corroborate our theory with experiments showing that when agents observe spatial paths,
the amount of memory required to learn a performant policy is reduced. Interestingly, this
effect arises unintentionally, and implicitly through the agent’s sensory stream. We discuss the
implications of our findings, and show they satisfy qualitative properties previously used to
ground accounts of external memory. Moving forward, we anticipate further work on this sub-
ject could reveal principled ways to exploit the environment as a substitute for explicit internal
memory.
Contribution(s)
1. We introduce a formalism for how the environment can functionally serve as an agent’s
memory (Section 3). Central to our formalism is the concept of artifacts (Definition 1),
which we define as observations that inform the past, and external memory (Definition 3).
Context: Prior work has hypothesized about externalizing memory (Clark & Chalmers,
1998; Sutton, 2003), but without a precise mathematical characterization of the phenomena.
2. The Artifact Reduction Theorem (Theorem 1): our main theoretical result proves artifacts
(Definition 1) reduce the information needed to represent history.
Context: The formalism we introduce naturally raises the question of what formal proper-
ties can be established.
3. Empirical evidence that RL agents can use their environment as a form of memory.
Context: Prior work, including our proposed theory, suggests that RL agents can external-
ize memory. Yet empirical evidence supporting this claim remains absent.
4. An argument that spatial artifacts from our experiments satisfy qualitative memory proper-
ties (Michaelian, 2012) used to ground accounts of externalized memory (Section 5).
Context: Our theoretical results establish a link between artifacts and memory, and our
empirical results provide evidence that artifacts can reduce memory demands. However, the
nature of memory we study requires further contextualization.
Artifacts as Memory Beyond the Agent Boundary John D. Martin1,2,† , Fraser Mince3,† , Esra’a Saleh3,4,5 , Amy Pajak3,6 john.martin@openmindresearch.org, frasermince@gmail.com, esraa.saleh@mila.quebec, pajak@seas.upenn.edu
1 Openmind Research Institute 2 University of Alberta 3 Cohere Labs Community 4 Université de Montréal 5 Mila – Québec AI Institute 6 University of Pennsylvania † Equal contribution
Abstract
The situated view of cognition holds that intelligent behavior depends not only on in-
ternal memory, but on an agent’s active use of environmental resources. Here, we begin
formalizing this intuition within Reinforcement Learning (RL). We introduce a mathe-
matical framing for how the environment can functionally serve as an agent’s memory,
and prove that certain observations, which we call artifacts, can reduce the information
needed to represent history. We corroborate our theory with experiments showing that
when agents observe spatial paths, the amount of memory required to learn a perfor-
mant policy is reduced. Interestingly, this effect arises unintentionally, and implicitly
through the agent’s sensory stream. We discuss the implications of our findings, and
show they satisfy qualitative properties previously used to ground accounts of exter-
nal memory. Moving forward, we anticipate further work on this subject could reveal
principled ways to exploit the environment as a substitute for explicit internal memory.
1 Introduction
According to the situated view of cognition, competent action depends not only on internal memory, but on an agent’s use of environmental resources (Hutchins, 1995; Clark, 1998; Menary, 2010). On some accounts, the environment itself can implicitly function as an agent’s memory (Clark & Chalmers, 1998; Sutton, 2003). In this paper, we aim to formalize such cases within Reinforcement Learning (RL). As a first step, we focus on one form of externalized memory which centers on the use of artifacts (Hutchins, 2001) to store information about an agent’s previous interactions—for instance, a trail of breadcrumbs indicating where the agent has been before. We make three main contributions. First, we introduce a mathematical framing for how the environ- ment can functionally serve as an agent’s memory. Our framework grounds the concept of artifacts as observations that inform the past (Definition 1), and proves the amount of information needed to represent a history is reduced when artifacts are present (Theorem 1). We equate externalized mem- ory to a condition on the amount of capacity needed to learn a performant policy (Definition 3), and show the amount of externalized memory can be systematically quantified. Our proposed method compares the capacity needed to match performance across two settings that differ in whether the agent can observe behavioral artifacts, such as a spatial path. Second, we empirically confirm that RL agents can use spatial environments as a form of memory. We find evidence for this in a five different settings and from two core agent designs: Q-learning
1
(Watkins & Dayan, 1992) and DQN (Mnih et al., 2015). In each case, we find the use of exter- nal memory arises unintentionally; leaving behind a spatial path—like a trail of breadcrumbs—is enough for the agent to experience the effect. Third, we place our results in a broader conceptual context and show that they satisfy qualitative properties previously used to ground accounts of external memory (Michaelian, 2012; Sims & Kiver- stein, 2022). We discuss our results, and suggest that further work in this area could yield principled ways to exploit the environment as a substitute for explicit internal memory.
2 The Reinforcement Learning Formalism
We adopt a purely experiential framing of RL, inspired by observable operator models (Jaeger, 2000), predictive state representations (Littman et al., 2001; Singh et al., 2004), and other general- izations of RL (Hutter, 2005; Dong et al., 2022; Abel et al., 2023; Bowling et al., 2023). Experiential models are appealing because they make few assumptions and are grounded entirely in observable data. That said, alternative frameworks such as POMDPs (Kaelbling et al., 1998) remain available.
Interaction. At every moment t ∈ N, an agent draws on its sense-data ot ∈ O, takes an action at ∈ A, then observes the outcome through the updated observation ot+1 ∈ O and scalar reward rt+1 ∈ R. We assume the sets O, A and R are all finite. In episodic settings, this interaction repeats until a termination condition is met, after which the interaction reinitializes. Traces of interaction are described by sequences of observations and actions, called histories. From the agent’s perspective, a single history is h = o1 a1 , o2 a2 , · · · , coming from the set of all histories H ≡ (O × A)∗ .
Bounded Agents. We study agents with bounded representations and input channels, defining a bounded agent in two parts relative to a history-dependent agent λ : H × O → ∆(A) over interface (O, A). First, an agent has a bounded representation if it possesses a finite set of internal states S, defined formally as π : S ×O → ∆(A), where there exists some s ∈ S such that λ(·|h) = π(·|s) for all h ∈ H (Abel et al., 2023). Second, an agent has a bounded input channel if its observations are filtered through a fixed mapping τ : X → O, which we call the transduction function1 , taking the full set of observable signals X to the agent-accessible signals O ⊆ X (Delchamps, 1990; Brockett & Liberzon, 2000). We consider two transduction functions: a linear projection T , such that o = T x for all x ∈ X , and the identity. A bounded agent is thus characterized by the triple (S, π, τ ), where S constrains the internal representation, π governs behavior, and τ determines the signals received from the environment2 . Correspondingly, the environment is a stochastic mapping ξ : G → ∆(X ) over the interface (A, X ), where G ≡ (X × A)∗ denotes the set of finite environment histories.
Objective. RL agents adapt to maximize the occurrence of future reward, which we capture by the discounted sum Rt+1 + γRt+2 + γ 2 Rt+3 + · · · , taking γ ∈ [0, 1) as the discount factor. The action-value function is the expected discounted sum following action a from history h in ξ: "∞ # X k q(h, a) = Eλ,ξ γ Rt+k+1 Ht = h, At = a . k=0
Learning. We consider bounded agents that learn an approximate action value q̂(o, a) ≈ q(h, a). Here, we suppress the dependence of the internal state s ∈ S, but assume s carries a set of learnable parameters along with additional overhead. The agent behaves according to an ϵ-greedy policy, se- lecting a uniform-random action with probability ϵ and otherwise selecting a ∈ arg maxa∈A q̂(o, a). 1 The transduction function is part of the environment controlled by design. For example, consider a resource-constrained
robot with a camera. The camera is part of the environment and chosen by the designer. If the camera provides n × n images, and the robot is only equipped to support m × m images, where m < n, transduction models a morphological constraint of the agent’s embodiment. 2 In contrast to partially-observed formulations, which map between latent and observable variables, the transduction
function maps exclusively between sets of observable variables. This distinction allows us to remain in the experiential setting, and to compare the performance of agents with different input channels within the same environment and task.
2
Two learning methods are relevant to our study: Linear Q-learning (Bradtke, 1992) and the Deep Q-Network (DQN) (Mnih et al., 2015). Linear Q-learning represents q̂ with a weighted sum of the observation-inputs: q̂(o, a; w) ≡ wa⊤ o, where w ≡ {wa ∈ R|O| , a ∈ A}. Given a sample transition, (o, a, r, o′ ), weights wa are updated with the Q-learning rule (Watkins & Dayan, 1992), using a constant, scalar step-size α > 0:
wa ← wa + α[r + γ max
′
q̂(o′ , a′ ; w) − q̂(o, a; w)]o.
a ∈A
DQN represents q̂ with a neural network of real-valued weights θ. Network weights are updated with backpropagation to minimize the following loss over mini-batches of cached experience D.
1 X
L(θ) = [r + γ max q̂(o′ , a′ ; θ′ ) − q̂(o, a; θ)]2 .
2 ′
a ∈A
(o,a,r,o′ )∈D
Following Mnih et al. (2015), we employ a target network with separate weights θ′ .
System Capacity. Let C ∈ N denote an agent’s capacity: the total internal memory available for learning. Similar to (Tamborski & Abel, 2025), we adopt an operational measure of capacity proportional to the number of learnable parameters: C ∝ |wa | for Linear Q-learning and C ∝ |θ| for DQN, excluding the replay buffer as a constant factor.
3 A Formalism of Externalized Memory
RL treats memory as an internal resource whose capacity is specified at design-time and generally assumed to remain constant throughout operation. In this section, we formalize what it means to externalize memory through the use of artifacts.
3.1 Artifacts as Memory
Here, artifacts are features of the environment that help an agent remember its past. Examples are ubiquitous: a folded page, a string tied around a finger, a trail of footprints in the snow. We specif- ically formalize artifacts that affect perception (Heersmink, 2021): those in which some present observation reliably encodes information about the past, enabling an agent to recover that informa- tion through observation alone. Definition 1 (Artifact). An artifact is an observation o, provided that for any t, if Ot = o, there exists some non-zero t′ < t and o′ ̸= o such that Ot′ = o′ . We say o is the artifact of o′ .
Our definition establishes a fine-grained condition of certainty for a single observation from the past. For a given environment ξ, the set of all artifacts Ωξ ⊆ O is the collection of observations satisfying Definition 1. We give a special name to environments that support this condition. Definition 2 (Artifactual Environment). An environment is artifactual if and only if Ωξ is non-empty. Example 1 (Page Keeping). Alice is an avid reader of books. Like many, she reads only a few pages at a time. Instead of remembering the page number where she stopped, she marks her place by folding the corner of the page. When she picks up the book later, she unfolds the corner and continues to read. This interaction can be represented by the artifactual environment pictured in Figure 1. Observa- tions indicate three basic situations where Alice sees a folded page (A), an unfolded page (B), or something unrelated (C). Whenever Alice observes A, she knows that B must have occurred. Thus, in this context, a folded page serves as an artifact.
The existence of artifacts can be expressed as a probabilistic property of the environment. Proofs of formal claims are provided in Section A of the Supplement.
3
B
0.5 B Alice observes: C, B, C, C, A, B, A, . . .
0.3 • Observing A ⇒ B occurred earlier.
s0 s1
C C • At t = 5, O5 = A ⇒ ∃ k ≥ 1 : O5−k = B. 0.5 A 0.4 • Specifically, for k = 3: O2 = B. 0.3 A: folded page ... B: unfolded page
C B C C A B A
C: unrelated
Time
t1 t2 t3 t4 t5 t6 t7
Figure 1: Page Keeping example: Transitions are labeled with probabilities and observations. Actions are omitted for clarity. Interaction starts from s0 . A is an artifact of B, and is only observed after s1 . Observing A at t = 5 implies that B was observed in the past: specifically at t = 2.
Lemma 1. An environment ξ is artifactual if, and only if, for any t > 0 there exist distinct observa- tions o, o′ , and non-zero t′ < t such that P(Ot′ = o′ |Ot = o) = 1.
Next, we present our main theoretical result, proving that artifacts reduce the amount of information needed to represent a history. In what follows let I(X; Y ) be the mutual information between two discrete random variables X and Y . Theorem 1 (Artifact Reduction). Let ξ be an artifactual environment, and let H be a history from ξ containing m > 1 observations and at least one artifact. There exists a reduced sequence H ′ with m − 1 observations, such that
I(Ot+1 ; H) = I(Ot+1 ; H ′ ).
The Artifact Reduction Theorem guarantees any history containing an artifact can be reduced by at least one observation. Thus, knowing H ′ is equivalent to knowing H, even though |H ′ | < |H|. The reduction increases when H contains multiple artifacts (Corollary 1); due to space constraints, this result is deferred to the Supplement. Importantly, reduction can only occur from distinct pairs of artifacts o and referents o′ . Otherwise, when multiple artifacts inform the same observation, their information becomes redundant.
3.2 Memory Beyond the Agent Boundary
An agent is said to externalize memory if achieving a goal requires greater internal capacity in the absence of environmental artifacts than it does when those artifacts are available. To quantify this condition, our method compares performance across two settings: an artifactual environment ξ and a corresponding control environment ξ ′ , defined as a copy of ξ with all artifactual properties removed. We formally define this control setting and prove its existence. Proposition 1 (Existence of an Artifactless Copy). For every artifactual environment ξ and any ϵ ∈ (0, 1), there exists a ξ ′ , called an artifactless copy of ξ, such that ξ ′ has the same observations, actions, rewards, and transition topology, but differs in its randomness, such that for all pairs (o, o′ ), with o ∈ Ωξ , and non-zero time-steps t′ < t, we have
P(Ot′ = o′ | Ot = o) ≤ 1 − ϵ.
Artifactless copies model common settings where observations provide no guarantee about what occurred in the past. Mathematically, the proof shows that an artifact can be obscured by adding noise to the observation distribution of ξ such that ξ ′ contains no artifacts: Ωξ′ = ∅.
4
We define the externalization of memory as a performance-matching condition on an agent’s internal capacity. Let P be a scalar performance measure (such as average, discounted, or total reward), and recall that an agent’s capacity is a scalar C > 0 proportional to the number of action-value parame- ters. Our definition applies to agents that share the same design and vary only in their capacity.
Definition 3: Externalizes Memory
Suppose agent π with capacity C achieves performance P in an artifactual environment ξ.
Let ξ ′ be an artifactless copy of ξ. Then π externalizes memory to ξ if any agent π ′ with
the same design as π and capacity C ′ ≤ C achieves performance P ′ < P in ξ ′ .
The residual C ′ − C serves as an upper bound on the amount of externalized memory.
4 Experiments
In this section, we present results from three experiments. All the experiments provide evidence that RL agents externalize memory in accordance with Definition 3. Data is gathered in a simulated domain, where agents learn to navigate while observing different spatial artifacts. In the first experi- ment, we consider the effect of learning in the presence of a shortest path. Here we find the strongest evidence of externalization. Our second experiment studies other artifacts of varying optimality. We find externalization is present with some but not others. In the third experiment, agents learn in a non-stationary environment, where a path is dynamically generated throughout interaction. Each experiment evaluates linear Q-learning and DQN agents over a range of capacities.
Environments. We consider simulated domains for spatial navigation, as in Figure 2, all sharing common dynamics. An agent explores a two-dimensional space with the goal of finding an unknown location. Locations come from a 13 × 13 grid. Each grid cell emits an 8 × 8 binary image, which only contains a small amount of salt and pepper noise (Boncelet, 2005). The noise patterns provide subtle but distinct markers to identify the states. Observations are composite images of 24 × 24 pixels, providing an allocentric view of the 3 × 3 region of cells surrounding the agent’s current location. The agent cannot observe walls; at boundary states, observations are padded by additional images to prevent the locations from appearing visually distinct from any other state. Transitions are deterministic and occur along the four cardinal directions. When the agent reaches the goal, it is rewarded with a bonus of +1. For all other transitions, it receives a zero-valued reward. Episodes terminate when the agent reaches the goal. Subsequently, the agent resets to the starting location to begin a new episode. Additional details are provided in Section B.3 of the Supplement.
4.1 Methodology
All three experiments follow a similar methodology. Learning performance is compared across two settings where the observability of an artifact differs. In one, an agent observes empty space with no visible artifacts (No Path, Figure 2a), and in the other a fixed artifact is observable (e.g. Figure 2b). We consider various spatial paths as artifacts, and we compare performance across these settings for a range of system capacities. Performance is quantified with both average and total reward.Pt Average reward measures an agent’s reward rate at any given time t > 0; we calculate this as 1t n=1 rn and note that is only achieved in the limit, as t approaches infinity. Total reward provides an aggregate measure summarizing PN the performance across an agent’s entire lifetime. The total reward over N time steps is n=1 rn . Following Definition 3, externalization is established by the relative performance of two agents: π and π ′ . Suppose π learns when artifacts are present, with capacity C and total reward of P . Separately, let π ′ be a learner restricted to the No Path setting, with capacity C ′ and total reward P ′ . Our experiments test the following condition.
5
Empirical Condition 1: Effective Memory Externalization
Whenever P ≥ P ′ and C < C ′ , we conclude that π has effectively externalized memory in
accordance with Definition 3.
We make thirty independent observations of performance, corresponding to different random initial- izations of the agent’s parameters. We use Empirical Condition 1 to define the alternative hypothesis of a one-sided statistical test (Section B.2). We reject at the 0.05 level then conclude there is suf- ficient evidence for memory externalization. We choose the most performant step-size for each capacity from a uniform grid search and report statistics from a separate evaluation. See the Supple- ment for additional details. We consider linear Q-learning agents that can have 16, 64, 256, 400, or 576 weights wa . These correspond to images of size 4 × 4, 8 × 8, 16 × 16, 20 × 20, 24 × 24, respectively. A capacity constraint is imposed on the input channel, through the transduction function, defined as a projection that selects the sub-image centered on the agent’s location. DQN agents use fully-connected ReLU networks of two or three layers. Specifically, we consider the set of networks produced by {2, 3} × {4, 8, 16, 32}, where the first set specifies the number of layers and the second is the number of hidden units per layer. The final layer for all networks has an output dimension equal to the number of actions. The transduction function is the identity.
(a) No Path (b) Optimal Path
Figure 2: The base environment used throughout experiments.
4.2 Learning in the Presence of a Minimum-length Path
This experiment compares performance across two domains: one in which the shortest path is visible (Optimal Path, Figure 2b), and one in which no path is visible (No Path, Figure 2a). Figure 3 shows plots of total reward for all agents and capacities. We find Empirical Condition 1 is satisfied in several cases. Consider the No Path linear agent with C ′ = 64 weights per action-value and the Optimal Path agent with C = 16 weights; we observe P > P ′ while C < C ′ . In other words, the necessary capacity to achieve comparable performance is reduced when the optimal path is visible. The amount of memory externalized is at most 48 = C ′ − C weights per action-value. Interestingly, this occurs below the theoretical minimum of 169 = 132 dimensions, as predicted by the rank of the matrix with every vectorized image. In this case, the agent can represent a relatively
6
12000 6000.0 No Path Optimal Path
No Path
10000 Optimal Path
4500.0
Total Reward
Total Reward
8000
6000 3000.0
4000
1500.0
2000
0 16 64 256 400 576 0.0 2x4 2x8 2x16 2x32 3x4 3x8 3x16 3x32
Capacity Network Size
Figure 3: Observing a spatial path reduces the necessary capacity to navigate. Averages of total reward for Linear Q-learning (left) and DQN (right) are shown, along with standard-error bars. We find that learning in presence of a shortest path improves performance for nearly every agent and capacity. Many improvements are statistically significant (see Supplement B.2).
0.05 No Path 0.05 Optimal Path
Capacity Capacity
0.04 16 0.04 16
Average Reward
Average Reward
64 64
0.03 256 0.03 256
400 400
576 576
0.02 0.02
0.01 0.01
0.000 50 100 150 200 0.000 50 100 150 200
Time Step (x 103) Time Step (x 103)
0.05 Network Size No Path 0.05 Network Size Optimal Path
2x4 2x4
2x8 2x8
0.04 2x16 0.04 2x16
Average Reward
Average Reward
2x32 2x32
3x4 3x4
0.03 3x8 0.03 3x8
3x16 3x16
3x32
0.02 0.02 3x32
0.01 0.01
0.000 25 50 75 100 0.000 25 50 75 100
Time Step (x 103) Time Step (x 103)
Figure 4: Performance improves when agents observe the shortest path: Average reward tends to increase when the shortest path is visible. This can be observed for nearly every capacity of Linear-Q and DQN; it appears most significant for higher capacity systems, but also has a stark affect in the low capacity regime. Averages and standard error regions are computed with 30 seeds.
simple policy that indexes on the optimal path; in particular, conjunctions of a few horizontal and vertical pixels suffice to represent a reliably rewarding action. The effect is also apparent with other capacities and in the deep RL setting, e.g. DQN with 3 × 16 and 3 × 32. Due to space constraints, we defer further analysis to Supplement B.4. Average reward is plotted in Figure 4. This quantity shows how the shortest path affects learning performance throughout an agent’s lifetime. The effect is stark in the low-capacity regime; without a path, linear agents are unable to reach the goal with less than 256 weights; with a path, they reliably reach the goal. DQN also experiences a performance boost with near uniformity across the range of
7
the considered network sizes. All the points at which externalization is significant are tabulated in Supplement B.
4.3 Learning in the Presence of Other Fixed Artifacts
This experiment repeats the previous performance comparison with four additional artifacts. Now we ask whether the impact on performance varies with the quality of behavior expressed by a given path. In addition, we evaluate learning in the presence of a non-behavioral artifact: a set of geometric landmarks. These help us to understand if externalization is possible without an overt behavioral signal, like a goal-directed path. Each artifact is listed below and illustrated in Figure 5. • Random: a path generated with uniform random actions (Figure 5a). • Suboptimal: a path that reaches the goal with a few more steps than optimal (Figure 5b). • Misleading: a path that steers toward the goal then veers off (Figure 5c). • Landmarks: geometric structures of various sizes, shapes, and locations (Figure 5d).
(a) Random (b) Suboptimal (c) Misleading (d) Landmarks
Figure 5: Environments considered for learning in the presence of other fixed artifacts.
Figure 6 shows plots of total reward for every artifact and across the previous range of capacities. We find linear agents externalize memory with all four artifacts, though to varying degrees. For instance, Random Path with C = 256 vs No Path with C ′ = 400. Such examples rule out the simple hypothesis that agents merely follow paths, because performance would otherwise be comparable to No Path. Our Landmarks baseline provides further support for this interpretation: specifically for C = 256 and C ′ = 400. The same story applies to DQN, which we find externalizes memory with the Suboptimal, Random, and Landmarks baselines. We evaluate an expanded range of capacities for the linear agent in Figure 12, provide plots of average reward and tabulated results in Appendix B.
4.4 Learning in the Presence of a Dynamic Path
This experiment moves to a more naturalistic setting in which the artifact is generated by an agent’s own behavior (Figure 7). Specifically, as the agent moves through the environment, a noisy path appears at visited locations and gradually fades until it is indistinguishable from the background. Given the non-stationary nature of this environment, we restrict our analysis to linear Q-learning, which is capable of tracking non-stationarity; conventional DQN, relying on a replay buffer, was unable to learn a performant policy in such settings. We repeat our test for externalized memory. Figure 7 shows plots of total reward. Empirical Condition 1 is satisfied at C = 256 weights per action value. Weaker evidence of externalization occurs for C = 400 at the 0.11 level. Similar to our other experiments, the presence of an artifact path appears to uniformly increase total reward across the range of capacities. Average reward curves and tabulated results are provided in Appendix B.
8
12000 No Path Misleading Path
10000 Random Path Suboptimal Path
Landmarks Optimal Path
Total Reward 8000 6000 4000 2000 0 16 64 256 400 576 Capacity 6000.0 No Path Misleading Path Random Path Suboptimal Path 4500.0 Landmarks Optimal Path Total Reward
3000.0
1500.0
0.0 2x4 2x8 2x16 2x32 3x4 3x8 3x16 3x32
Network Size
Figure 6: Externalization arises with other fixed artifacts: Average total reward is observed for three paths and one set of geometric landmarks. We find evidence of externalizing memory across all artifacts and with the following number of instances for linear agents: Suboptimal (3), Misleading (2), Random (2), Landmarks (1). For DQN, Suboptimal (2), Landmarks (2), Random (1), Misleading (0). Each bar presents an average and standard-error from the 30 seeds shown.
12000 No Path
10000 Dynamic
Total Reward
8000
6000
4000
2000
0 16 64 256 400 576
Capacity
Figure 7: Externalization with a dynamic path: The left panel illustrates the environment, in which the current policy generates a path vanishing over time. We observe performance uniformly increase over nearly all capacities and Empirical Condition 1 satisfied for C = 256.
5 Discussion
Artifactual Environments and Classical Memory. Some readers may wonder how artifactual environments express the basic encode-store-retrieve functionality of classic memory models, such as those Klein (2015) and Michaelian & Sutton (2017) describe. Artifacts meet the first requirement
9
by virtue of being observations that provide information about an agent’s history (Definition 1). In the environments we study, information is anchored to locations in space; data is written upon first visiting a location, then later retrieved by returning to it. In this way, spatial artifacts function as memory records with an access protocol dictated by the environment and interface (O, A).
Artifacts as Situated Memory. Situated accounts of memory enrich the classical model by grounding memory’s purpose in service of decision-making (Clark & Chalmers, 1998). In regards to external memory, Michaelian (2012) argues that a model must satisfy certain criteria to capture the essential functionality of natural memory. Michaelian requires agents have constant access to an information-bearing resource and some process to determine the information’s relevance. Following Sims & Kiverstein (2022), we summarize these in three points: 1. Survival relevant: a memory should bring positive value to decision making. 2. Susceptible to change: memories are mutable. 3. Selection: a memory’s relevance is determined through some selection process. The first requirement underscores the cost of storage. As Sims & Kiverstein (2022) put it: memory must be “worth its weight in terms of long-term fitness benefits.” The second point preserves the basic functionality of the encode-store-retrieve model, while the third requires the existence of a process to determine a memory’s relevance in a given scenario. Sims & Kiverstein (2022) use these desiderata to argue the spatial trails left behind by slime mold (Reid et al., 2012) function as external memory. We similarly argue that the artifacts from our em- pirical study satisfy these desiderata. In support of (1), note that an artifact’s value is immediately apparent from total reward (see Figures 3, 6, and 7); agents in artifactual environments consistently accumulate more reward than in artifactless environments. Support for (2) follows directly from the encode-store-retrieve model, to which artifacts from the Dynamic Path conform (see Figure 7). Fixed artifacts provide read-only information and yet still produce an external memory effect, sug- gesting that reading is more fundamental than writing when learning to navigate and the desiderata may need further refinement. Support for (3) comes from the learning process. Through repeated credit assignment, policies that read and write on each step gradually improve and bias navigation toward goal-relevant locations. With these properties in place, we conclude the artifacts from our study support the same arguments and conclusions as previous accounts of external memory.
Unintentional Memory. Our experiments demonstrate that an agent can read and write informa- tion to the environment without any explicit objective directing it to do so. In each experiment, agents were given a standard navigation objective: a sparse reward signal providing a bonus for reaching the goal, but no explicit incentive to follow a path. Still, we observe path-following behav- ior, as performance would otherwise match the No Path baseline. Moreover, in the Dynamic Path environment (Figure 7), agents record traces of their previous interactions without explict direction. These artifacts go on to guide future behavior. Remarkably, this form of emergent behavior requires no explicit design or human involvement; it emerges naturally as a consequence of reinforcement learning in a sufficiently complex environment.
Implications for Agent Design. A popular line of research pursues designs whose performance scales with the number of trainable parameters. This direction is motivated by milestone devel- opments (Silver et al., 2016; Brown et al., 2020; Fawzi et al., 2022), historical arguments for the primacy of computation (Sutton, 2019), and empirical findings of power-law relationships between system capacity and performance (Kaplan et al., 2020). Our results hint at another path: rather than scaling system resources, performance gains may instead arise from environments that coevolve with the agent. It is possible that current designs are already sufficient for competent, human-level performance, but require judicious pairing with an appropriate environment to scaffold problem solving (Sterelny, 2010). More work is needed to understand the laws governing the relationship between environment and agent design.
10
Limitations. A primary aim of this paper was to offer a purely observational account of external memory. However, our formalism raises the question of whether artifacts can be defined to en- compass action as well. Such an extension would be relatively straightforward, though validating it would require considering artifacts that encode previous actions. In a gridworld setting, this amounts to providing directional information, which our bidirectional spatial paths do not capture. Some may view the total certainty conveyed by artifacts as a limitation, arguing that a more general theory would incorporate a stochastic condition. We agree that not all forms of external memory need to guarantee knowledge transfer with total certainty. Yet even this simple assumption suffices to prove that artifacts reduce the information needed to represent the past (Theorem 1). Characterizing what guarantees can be made when artifacts provide only partial information remains an interesting direction for future work.
6 Related Work
Memory in RL. Classical memory is any state or process resulting from the sequence of encoding, storing, and retrieving information (Klein, 2015; Gazzaniga, 2009; Bernecker & Michaelian, 2017). In RL, the term ‘memory’ refers to several distinct concepts and processes, such as the agent’s func- tional dependence on the past (Littman, 1994; Singh et al., 1994; Mnih et al., 2015; Abel et al., 2023; Icarte et al., 2020), the representational capacity of its internal state (Dong et al., 2022; Sutton & Barto, 2018; Tamborski & Abel, 2025), even the specific use of recurrent architectures (Hausknecht & Stone, 2015) or replay buffers (Lin, 1992; Schaul et al., 2016). In other contexts, the term applies more broadly to any learnable parameters or writable storage (Oh et al., 2016; Khan et al., 2018). Our work studies memory as it pertains to the representational capacity of a value function. We argue that a certain, fixed amount of capacity is required to achieve a goal, and when this memory foot- print is reduced in the presence of artifacts, the deficit must be compensated for by the environment (Figures 3, 6, 7).
Artifacts are Episodic Memories. Memory can be taxonomized by the content it provides. Model-free RL agents acquire procedural memory, also known as habit memory (Russell, 1921; Michaelian & Sutton, 2017). We study procedural memory in the context of a value function. In our work, the content of an artifact couples with the weights of a value function to inform the agent how to navigate. Recall an environment is artifactual when a given observation o determines one of the past P(Ot′ = o′ | Ot = o) = 1. Thus, on their own, artifacts constitute a kind of episodic memory: knowledge of ones personal past (Tulving, 1972). Several works argue for the centrality of episodic memory in natural agents (Gershman & Daw, 2017; Lengyel & Dayan, 2007) and in AI systems (Blundell et al., 2016; Hu et al., 2021; Pritzel et al., 2017; Lin et al., 2018; Zhu* et al., 2020). Thus, artifacts are episodic memories that reduce procedural memory.
The Memory of Artificial Agents. The notion of individuated memory has long structured com- putational models of agency. Early models treat agents as unified systems with centralized memory encoding beliefs about the world (Newell, 1990; Anderson, 1993; Rao & Georgeff, 1995). Later models reconceive agents as networks of reactive units (Brooks, 1986; 1991; Arkin, 1998). In these architectures, memory is distributed but remains individuated: there is no notion of memory exist- ing outside the agent boundary. Distribution across units reflects an internal architectural choice rather than any dissolution of that boundary. Reinforcement learning agents, similarly, are bounded systems that acquire knowledge through trial and error (Kaelbling et al., 1998; Sutton, 2022; Dong et al., 2022; Abel et al., 2023). While committing to few assumptions about centralization, they maintain localized memory in the form of value functions, state representations, world models, and other sources of computational overhead. Relation to Stigmergy. Stigmergy is a mechanism of behavioral coordination arising from interac- tions between a decision-maker and artifacts in their environment (Heylighen, 2015; Thierry et al., 1995; Ricci et al., 2007). The concept of stigmergy was introduced by Grassé (1959) to explain the highly coordinated behavior of termites. Traditionally, stigmergy research has focused on the
11
self-organization of many simple agents operating under fixed policies. A canonical example is the formation of pheromone trails, which guide ants to food sources (Wilson, 1962; Sumpter & Beek- man, 2003). Definition 2 formalizes a type of environment that bears resemblance to those studied in stigmergic research. In such settings, we study individual RL agents adapting to the context af- forded by spatial artifacts. Martín Muñoz (1998) and Peshkin et al. (1999) study RL in stigmergic settings, both assuming that the environment exposes explicit memory states for agents to manip- ulate through action. In contrast, we study settings where memory effects are implicitly realized through environment dynamics and the conventional, unprivileged sensory stream.
The Artifacts of Other Agents. The setting from our fixed-artifact experiments is similar to that studied by Borsa et al. (2019), in which a deep RL agent learns from observing another agent without explicitly modeling it or having access to its internal state. The fixed artifacts we consider could plausibly originate from another agent’s behavior. In our dynamic-path experiments, by contrast, agents learn from traces of their own prior behavior. Importantly, we focus on how behavioral artifacts affect memory, and therefore restrict our analysis to architectures that condition only on the current observation; Borsa et al. (2019), by contrast, employs recurrent architectures.
7 Conclusion
We investigate the relationship between an RL agent’s computational resources and its environment, providing evidence that, in artifactual settings, the environment can serve as a form of external memory. This effect holds across multiple capacities, algorithms, and environments. We formalize artifactual environments and prove that such settings afford a reduction in the number of observa- tions required to represent a history. We further argue that the externalized memory observed in our experiments satisfies the criteria established by prior accounts of external memory. Together, our results suggest that a memory process is not confined to one side of the conventional agent- environment boundary; rather, its data and functionality can cut across this boundary and reside in the environment. Future work can progress naturally along two directions: agent design and agent-environment re- lationships. A concrete next step would be to investigate whether agents can adapt their capacity to the presence of artifacts—to modulate plasticity between different processes. Our work studied unintentional externalization, so a natural question is whether agents can intentionally generate ar- tifacts from which they later benefit. One might also formalize artifacts differently; we studied only artifacts that determine a single past observation, but in principle artifacts are richer structures that may determine multiple past observations. More broadly, we anticipate that further work in this area could reveal principled ways to exploit the environment as a substitute for explicit internal memory, and shed additional light on what memory means for artificial agents.
Acknowledgments
The authors would like to thank Will Dabney, Shruti Mishra, Joseph Modayil, and Matt Taylor for their comments on an early draft of this paper, and the members of the Openmind Research Institute for thoughtful discussions that guided this project.
References David Abel, André Barreto, Hado van Hasselt, Benjamin Van Roy, Doina Precup, and Satinder Singh. On the convergence of bounded agents. arXiv preprint arXiv:2307.11044, 2023.
John R. Anderson. Rules of the Mind. Lawrence Erlbaum Associates, Hillsdale, NJ, 1993. ISBN 978-0805812343.
Ronald C. Arkin. Behavior-based Robotics. The MIT Press, Cambridge, MA, 1998.
12
Sven Bernecker and Kourken Michaelian (eds.). The Routledge Handbook of Philosophy of Memory. Routledge, New York, 1st edition, 2017. ISBN 9781138909366.
Peter J. Bickel and Kjell A. Doksum. Mathematical Statistics: Basic Ideas and Selected Topics, Volumes I–II Package. Chapman and Hall/CRC, 1st edition, 2015. ISBN 9781498740319.
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Z. Leibo, Jack Rae, Daan Wierstra, and Demis Hassabis. Model-free episodic control. arXiv preprint arXiv:1606.04460, 2016.
Charles G. Boncelet. Image noise models. In Al Bovik (ed.), Handbook of Image and Video Processing, pp. 397–409. Academic Press, 2nd edition, 2005. ISBN 9780121197926. DOI: 10.1016/B978-012119792-6/50087-5.
Diana Borsa, Nicolas Heess, Bilal Piot, Siqi Liu, Leonard Hasenclever, Remi Munos, and Olivier Pietquin. Observational learning by reinforcement learning. In Proceedings of the 18th Interna- tional Conference on Autonomous Agents and Multi-agent Systems, AAMAS ’19, pp. 1117–1124, Richland, SC, 2019. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9781450363099.
Michael Bowling, John D Martin, David Abel, and Will Dabney. Settling the reward hypothesis. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 3003–3020. PMLR, 23–29 Jul 2023.
Steven Bradtke. Reinforcement learning applied to linear quadratic regulation. In S. Hanson, J. Cowan, and C. Giles (eds.), Advances in Neural Information Processing Systems, volume 5. Morgan-Kaufmann, 1992.
Roger W. Brockett and Daniel Liberzon. Quantized feedback stabilization of linear systems. IEEE Transactions on Automatic Control, 45(7):1279–1289, July 2000. DOI: 10.1109/9.867021.
Rodney A. Brooks. A robust layered control system for a mobile robot. IEEE Journal on Robotics and Automation, 2(1):14–23, 1986. DOI: 10.1109/JRA.1986.1087032.
Rodney A. Brooks. Intelligence without representation. Artificial Intelligence, 47(1):139–159, 1991. ISSN 0004-3702. DOI: https://doi.org/10.1016/0004-3702(91)90053-M.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33:1877–1901, 2020.
Andy Clark. Being there: Putting brain, body, and world together again. MIT press, 1998.
Andy Clark and David Chalmers. The extended mind. Analysis, 58(1):7–19, 1998.
David F. Delchamps. Stabilizing a linear system with quantized state feedback. IEEE Transactions on Automatic Control, 35(8):916–924, August 1990.
Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou. Simple agent, complex environment: efficient reinforcement learning with agent states. Journal of Machine Learning Research, 23(1), January 2022. ISSN 1532-4435.
Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Moham- madamin Barekatain, Alexander Novikov, Francisco J R. Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930):47–53, 2022.
13
Michael S. Gazzaniga (ed.). The Cognitive Neurosciences. The MIT Press, 9 2009. ISBN 9780262303101. DOI: 10.7551/mitpress/8029.001.0001.
Samuel J. Gershman and Nathaniel D. Daw. Reinforcement learning and episodic mem- ory in humans and animals: An integrative framework. Annual Review of Psychology, 68(Volume 68, 2017):101–128, 2017. ISSN 1545-2085. DOI: https://doi.org/10.1146/ annurev-psych-122414-033625.
Pierre-Paul Grassé. La reconstruction du nid et les coordinations interindividuelles chez bellicositer- mes natalensis et cubitermes sp. la théorie de la stigmergie: Essai d’interprétation du comporte- ment des termites constructeurs. Insectes Sociaux, 6(1):41–80, March 1959. ISSN 1420-9098. DOI: 10.1007/BF02223791.
Matthew Hausknecht and Peter Stone. Deep recurrent q-learning for partially observable mdps. In AAAI Fall Symposium Series: Sequential Decision Making for Intelligent Agents, pp. 29–37, 2015.
Richard Heersmink. Varieties of artifacts: Embodied, perceptual, cognitive, and affective. Topics in Cognitive Science, 13(4):573–596, 2021. DOI: 10.1111/tops.12549.
Francis Heylighen. Stigmergy as a universal coordination mechanism: Components, varieties and applications. https://pespmc1.vub.ac.be/Papers/Stigmergy-Springer.pdf, 2015.
Hao Hu, Jianing Ye, Guangxiang Zhu, Zhizhou Ren, and Chongjie Zhang. Generalizable episodic memory for deep reinforcement learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 4380–4390. PMLR, 18–24 Jul 2021.
Edwin Hutchins. Cognition in the Wild. The MIT Press, 02 1995. ISBN 9780262275972.
Edwin Hutchins. Cognitive artifacts. In The MIT Encyclopedia of the Cognitive Sciences, pp. 126– 127. MIT Press, Cambridge, MA, 2001.
Marcus Hutter. Universal Artificial Intelligence. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin, Heidelberg, 1st edition, 2005. ISBN 978-3-540-22139-5. DOI: 10.1007/ b138233.
Rodrigo Toro Icarte, Richard Valenzano, Toryn Q. Klassen, Phillip Christoffersen, Amir massoud Farahmand, and Sheila A. McIlraith. The act of remembering: a study in partially observable reinforcement learning, 2020.
Herbert Jaeger. Observable operator models for discrete stochastic time series. Neural Computation, 12(6):1371–1398, 06 2000. ISSN 0899-7667. DOI: 10.1162/089976600300015411.
Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1-2):99–134, 1998. ISSN 0004-3702. DOI: https://doi.org/10.1016/S0004-3702(98)00023-X.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020.
Arbaaz Khan, Clark Zhang, Nikolay Atanasov, Konstantinos Karydis, Vijay Kumar, and Daniel D. Lee. Memory augmented control networks. In International Conference on Learning Represen- tations, 2018.
Stanley B. Klein. What memory is. WIREs Cognitive Science, 6(1):1–38, 2015. DOI: https://doi. org/10.1002/wcs.1333.
14
Máté Lengyel and Peter Dayan. Hippocampal contributions to control: The third way. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20, pp. 889–896, 2007.
Long-Ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine Learning, 8(3):293–321, May 1992. ISSN 1573-0565. DOI: 10.1007/BF00992699.
Zichuan Lin, Tianqi Zhao, Guangwen Yang, and Lintao Zhang. Episodic memory deep q-networks. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pp. 2433–2439. International Joint Conferences on Artificial Intelligence Organization, 7 2018. DOI: 10.24963/ijcai.2018/337.
Michael L. Littman. Memoryless policies: theoretical limitations and practical results. In Proceed- ings of the Third International Conference on Simulation of Adaptive Behavior: From Animals to Animats 3: From Animals to Animats 3, SAB94, pp. 238–245, Cambridge, MA, USA, 1994. The MIT Press. ISBN 0262531224.
Michael L. Littman, Richard S. Sutton, and Satinder Singh. Predictive representations of state. In T. Dietterich, S. Becker, and Z. Ghahramani (eds.), Advances in Neural Information Processing Systems, volume 14, pp. 1555–1561, 2001.
Mario Martín Muñoz. Reinforcement Learning for Embedded Agents Facing Complex Tasks. Phd thesis, Universitat Politècnica de Catalunya, Barcelona, Spain, 1998.
Richard Menary. Cognitive integration and the extended mind. The extended mind, pp. 227–243, 2010.
Kourken Michaelian. Is external memory memory? biological memory and extended mind. Con- sciousness and Cognition, 21(3):1154–1165, 2012. ISSN 1053-8100. DOI: https://doi.org/10. 1016/j.concog.2012.04.008.
Kourken Michaelian and John Sutton. Memory. In Edward N. Zalta (ed.), The Stanford Ency- clopedia of Philosophy. Metaphysics Research Lab, Stanford University, Summer 2017 edition, 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529–533, February 2015. ISSN 1476-4687. DOI: 10.1038/nature14236.
Allen Newell. Unified Theories of Cognition. Harvard University Press, Cambridge, MA, 1990. ISBN 9780674920996.
Junhyuk Oh, Valliappa Chockalingam, Satinder Singh, and Honglak Lee. Control of memory, ac- tive perception, and action in minecraft. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceed- ings of Machine Learning Research, pp. 2790–2799, New York, New York, USA, 20–22 Jun 2016. PMLR.
Andrew Patterson, Samuel Neumann, Martha White, and Adam White. Empirical design in re- inforcement learning. Journal of Machine Learning Research, 25(318):1–63, 2024. URL https://jmlr.org/papers/v25/23-0183.html.
Leonid Peshkin, Nicolas Meuleau, and Leslie Pack Kaelbling. Learning policies with external mem- ory. In Proceedings of the 16th International Conference on Machine Learning, ICML ’99, pp. 307–314, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1558606122.
15
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. 2827–2836. PMLR, 06–11 Aug 2017.
Anand S. Rao and Michael P. Georgeff. BDI agents: From theory to practice. In Proceedings of the First International Conference on Multi-Agent Systems (ICMAS-95), pp. 312–319, 1995.
Chris R Reid, Tanya Latty, Audrey Dussutour, and Madeleine Beekman. Slime mold uses an ex- ternalized spatial “memory” to navigate in complex environments. Proceedings of the National Academy of Sciences, 109(43):17490–17494, 2012.
Alessandro Ricci, Andrea Omicini, Mirko Viroli, Luca Gardelli, and Enrico Oliva. Cognitive stig- mergy: Towards a framework based on agents and artifacts. In Danny Weyns, H. Van Dyke Parunak, and Fabien Michel (eds.), Environments for Multi-Agent Systems III, pp. 124–140. Springer, 2007. ISBN 978-3-540-71103-2.
Bertrand Russell. The Analysis of Mind. G. Allen & Unwin, London, 1921.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In International Conference on Learning Representations, 2016.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484–489, 2016.
Matthew Sims and Julian Kiverstein. Externalized memory in slime mould and the extended (non- neuronal) mind. Cognitive Systems Research, 73:26–35, 2022. ISSN 1389-0417. DOI: https: //doi.org/10.1016/j.cogsys.2021.12.001.
Satinder Singh, Michael R. James, and Matthew R. Rudary. Predictive state representations: a new theory for modeling dynamical systems. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, UAI ’04, pp. 512–519, Arlington, Virginia, USA, 2004. AUAI Press. ISBN 0974903906.
Satinder P. Singh, Tommi Jaakkola, and Michael I. Jordan. Learning without state-estimation in par- tially observable markovian decision processes. In William W. Cohen and Haym Hirsh (eds.), Ma- chine Learning Proceedings 1994, pp. 284–292. Morgan Kaufmann, San Francisco (CA), 1994. ISBN 978-1-55860-335-6. DOI: https://doi.org/10.1016/B978-1-55860-335-6.50042-8.
Kim Sterelny. Minds: extended or scaffolded? Phenomenology and the Cognitive Sciences, 9(4): 465–481, December 2010. ISSN 1572-8676. DOI: 10.1007/s11097-010-9174-y.
David J.T Sumpter and Madeleine Beekman. From nonlinearity to optimality: pheromone trail foraging by ants. Animal Behaviour, 66(2):273–280, 2003. ISSN 0003-3472. DOI: https://doi. org/10.1006/anbe.2003.2224.
John Sutton. Constructive memory and distributed cognition: Towards an interdisciplinary frame- work. In B. Kokinov and W. Hirst (eds.), Constructive Memory, pp. 290–303. New Bulgarian University, 2003.
Richard S. Sutton. The bitter lesson. Incomplete Ideas (blog), 2019. URL http://www. incompleteideas.net/IncIdeas/BitterLesson.html.
Richard S. Sutton. The quest for a common model of the intelligent decision maker. In Proceed- ings of the 5th Multi-disciplinary Conference on Reinforcement Learning and Decision Making (RLDM 2022), Providence, Rhode Island, USA, 2022.
16
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, Cambridge, MA, 2nd edition, 2018.
Massimiliano Tamborski and David Abel. Memory allocation in resource-constrained reinforcement learning. arXiv preprint arXiv:2506.17263, 2025. B. Thierry, G. Theraulaz, J.Y. Gautier, and B. Stiegler. Joint memory. Behavioural Processes, 35(1):127–140, 1995. ISSN 0376-6357. DOI: https://doi.org/10.1016/0376-6357(95)00039-9. Cognition and Evolution.
Endel Tulving. Episodic and semantic memory. In Organization of Memory, pp. 381–403. Academic Press, London, UK, 1972. Christopher J. C. H. Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3–4):279–292, May 1992. ISSN 1573-0565. DOI: 10.1007/BF00992698.
Edward O. Wilson. Chemical communication among workers of the fire ant solenopsis saevissima (fr. smith) 1. the organization of mass-foraging. Animal Behaviour, 10(1):134–147, 1962. ISSN 0003-3472. DOI: https://doi.org/10.1016/0003-3472(62)90141-0. Guangxiang Zhu, Zichuan Lin, Guangwen Yang, and Chongjie Zhang. Episodic reinforcement learning with associative memory. In International Conference on Learning Representations, 2020.
17
Supplementary Materials
The following content was not necessarily subject to peer review.
A Proofs
Lemma 1. An environment ξ is artifactual if, and only if, for any t > 0 there exist distinct observa- tions o, o′ , and non-zero t′ < t such that P(Ot′ = o′ |Ot = o) = 1.
Proof. Necessity: Suppose ξ is artifactual. Then Ωξ ̸= ∅, meaning there exists at least one o ∈ Ωξ satisfying Definition 1. According to Definition 1, for all times t where Ot = o, there exists some non-zero t′ < t and o′ ̸= o such that Ot′ = o′ . In terms of probability, if the event Ot = o logically necessitates that Ot′ = o′ , then the sample space is constrained such that there are no outcomes where Ot = o and Ot′ ̸= o′ . Mathematically, this implies:
P(Ot′ = o′ ∩ Ot = o)
P(Ot′ = o′ |Ot = o) =
P(Ot = o)
Since Ot = o implies Ot′ = o′ , the intersection Ot′ = o′ ∩ Ot = o is simply the event Ot = o:
Ot = o)
P(Ot′ = o′ |Ot = o) = = 1.
P(Ot = o)
Sufficiency: Suppose that for any t > 0, there exist distinct o, o′ and t′ < t such that P(Ot′ = o′ |Ot = o) = 1. This implies that the occurrence of o at time t provides total certainty about the occurrence of o′ at time t′ . If the probability of the past state o′ given the current state o is 1, then for every realization of the process where Ot = o, it must be that Ot′ = o′ . Since o′ is distinct from o, this satisfies the requirement in Definition 1. Because such an o exists, the set Ωξ is non-empty. Per Definition 2, the environment is therefore artifactual.
Theorem 1 (Artifact Reduction). Let ξ be an artifactual environment, and let H be a history from ξ containing m > 1 observations and at least one artifact. There exists a reduced sequence H ′ with m − 1 observations, such that
I(Ot+1 ; H) = I(Ot+1 ; H ′ ).
Proof. Since ξ is artifactual, by Lemma 1, there exist distinct observations o, o′ and non-zero times t, t′ with t′ < t such that P(Ot′ = o′ | Ot = o) = 1. Let H = Ot , At , Ot−1 , At−1 , . . . , Ot−m+1 , At−m+1 be an m-length history ending at time t. As- sume H contains both the observation o′ at time t′ = t − k and its artifact o at time t, where 1 ≤ k < m. Construct H ′ by removing the observation at time t − k:
H ′ = Ot , At , . . . Ot−k+1 , At−k+1 , At−k , Ot−k−1 , At−k−1 , . . . Ot−m+1 , At−m+1 .
Note that H ′ has m − 1 observations. By the chain rule for mutual information:
I(Ot+1 ; H) = I(Ot+1 ; H ′ ) + I(Ot+1 ; Ot−k | H ′ ).
18
Since Ot = o is in H ′ and P(Ot−k = o′ | Ot = o) = 1, the observation Ot = o completely determines Ot−k = o′ . Therefore, Ot−k is a deterministic function of the information already present in H ′ , which implies I(Ot+1 ; Ot−k | H ′ ) = 0. Thus,
I(Ot+1 ; H) = I(Ot+1 ; H ′ ).
This equality holds for all histories H with positive probability under the environment dynamics where observation o′ precedes its artifact o.
Proposition 1 (Existence of an Artifactless Copy). For every artifactual environment ξ and any ϵ ∈ (0, 1), there exists a ξ ′ , called an artifactless copy of ξ, such that ξ ′ has the same observations, actions, rewards, and transition topology, but differs in its randomness, such that for all pairs (o, o′ ), with o ∈ Ωξ , and non-zero time-steps t′ < t, we have
P(Ot′ = o′ | Ot = o) ≤ 1 − ϵ.
Proof. Let ξ be an artifactual environment. We construct an artifactless copy ξ ′ by adding noise to all the artifactual relationships. Consider the set of all artifactual relationships in ξ:
Z = {(i, j, k, t) : i, j ∈ O, i ̸= j, k ≥ 1, t > k, P(Xt−k = i | Xt = j) = 1}
For each (i, j, k, t) ∈ Z, modify the transition dynamics to ensure that when Xt = j, there is a small but non-zero probability ϵ > 0 that Xt−k ̸= i. Specifically, define ξ ′ such that: ( 1−ϵ : (i, j, k, t) ∈ Z Pξ′ (Xt−k = i | Xt = j) = Pξ (Xt−k = i | Xt = j) : otherwise
where the remaining probability mass ϵ is distributed among other possible values of Xt−k . By construction, for all distinct observations i, j and all integers k ≥ 1, t with t > k:
Pξ′ (Xt−k = i | Xt = j) ≤ 1 − ϵ < 1
Therefore, ξ ′ is non-artifactual, and the artifacts of ξ are obscured in ξ ′ .
A.1 Additional Results
Corollary 1. Suppose H is an m-length history containing k < m artifacts. There exists a history H ′ containing m − k observations such that
I(Ot+1 ; H) = I(Ot+1 ; H ′ ).
Proof. Starting with an m-length history Hm , define a history Hm−1 by removing the observation associated with a single artifact. According to the Artifact Reduction Theorem (Theorem 1), Hm and Hm−1 have the same mutual information with Ot+1 . Apply Theorem 1 starting from the reduced history of the previous application. After k applications, let H = Hm and H ′ = Hm−k . We have
I(Ot+1 ; H) = I(Ot+1 ; H ′ ).
19
B Experimental Details
B.1 Hyperparameter Selection
Our experiments treat step-size as a hyperparameter, sweeping over a finite set of candidate values to select the value yielding the highest total reward averaged across 30 seeds. To correct for maximiza- tion bias, we use a two-stage approach (Patterson et al., 2024). Specifically, we report the average and standard error of 30 different seeds for the hyperparameters with maximum performance. Fig- ures 10, 14, and 18 show the average total reward across the full range of step-sizes considered in each experiment. Note the plots exhibit distinct maximums most capacities.
B.2 Statistical Tests
We use a two-sample model to test whether the mean total reward from one agent is higher than another. Let Pi be a random sample of total rewards from an agent that learns in an artifactual environment. The subscript i indexes the agent’s capacity, e.g. 2 × 16. Similarly, let Qj denote the random sample of agent j in the artifactless environment (No Path). The empirical averages of each sample are respectively denoted p̄i and q̄j . We test every pair (i, j) according to the null hypothesis H0 (i, j) : p̄i ≤ q̄j at a significance-level of α = 0.05 For more information on two-sample models see Bickel & Doksum (2015).
B.3 Environment Details
Observations • Tile textures: randomly generated black-and-white patterns with 10% black pixels. • The agent observes a 3×3 portion of the grid centered on its current cell. • Walls are not explicitly visible; they are only apparent through self-looping transitions. • The agent’s position and goal location are not visible in observations.
Artifacts • Optimal Path: Shortest path from start to goal. • Suboptimal Path: A path 8 steps longer than optimal. • Misleading Path: Hand-crafted path that does not lead to the goal. • Random Path: A fixed path generated via random walk. • Landmarks: Multi-cell shapes (diamond, donut, circle, rectangle, triangle, square) distributed throughout the environment.
Dynamic Path Environment. Here, we describe the path dynamics (Figure 8). A path is drawn at every transition: from the current cell to the next. Let P be the set of pixels connecting the centers of both cells with a given thickness. Furthermore, let Q be set of all pixels. At every timestep, a subset of P (Num new path pixels) is drawn without replacement and uniformly at random. These pixels are assigned values of one to mark the path. These values persist into the future, until they are randomly selected for removal. At each step, a subset of Q (Num vanishing pixels) is drawn uniformly at random and without replacement. With a fixed probability (Vanishing rate), these pixels are assigned values of zero. The path is applied as a mask to the full image maintained by the environment. Thus, from the agent’s perspective, a value of zero removes the path and reveals the original background image of salt-and-pepper noise.
20
Parameter Value Linear Q-Learning Discount factor (γ) 0.95 Max episode length (steps) 1000 Start epsilon (ϵstart ) .1 End epsilon (ϵend ) 0.01 Exploration schedule period (steps) 100000 Path width (pixels) 3 DQN Optimizer Adam Replay buffer size 1,000,000 Minibatch size 16 Target network update frequency (steps) 500 Target network update rate 1.0 Discount factor (γ) 0.95 Max episode length (steps) 200 Start epsilon (ϵstart ) 1.0 End epsilon (ϵend ) 0.01 Exploration schedule period (steps) 50000 Path width (pixels) 3 Dynamic Environment Discount factor (γ) 0.95 Max episode length (steps) 1000 Start epsilon (ϵstart ) .1 End epsilon (ϵend ) 0.01 Exploration schedule period (steps) 100000 Num vanishing pixels 300 Vanishing rate 0.25 Num new path pixels 8 Path width (pixels) 1
Figure 8: Experiment Configuration Details. Hyperparameters used for linear agent (above), DQN agents (middle), dynamic experiments (below).
21
B.4 Experiment 1. Learning in the Presence of a Shortest Path
Figure 9: Environments considered in Experiment 1.
10000 No Path 10000 Optimal Path
Capacity
7500 16 7500
Total Reward
Total Reward
64 Capacity
256 16
5000 400 5000 64
576 256
2500 2500 400
576
0 0
4
8
02
04
08
2
4
4
8
02
04
08
2
4
00
00
0.0
0.0
00
00
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Step-size Step-size
5500 No Path 5500 Optimal Path
2x4 2x4
4125 2x8 4125 2x8
Total Reward
Total Reward
2x16 2x16
2x32 2x32
2750 3x4 2750 3x4
3x8 3x8
1375 3x16 1375 3x16
3x32 3x32
0 0
-05
-05
1
5
01
05
1
-05
-05
1
5
01
05
1
00
00
0.0
00
00
0.0
0.0
0.0
0.0
0.0
1e
5e
1e
5e
0.0
0.0
0.0
0.0
Step-size Step-size
Figure 10: Experiment 1. Step-size sweeps. Linear Q-learning (top half), DQN (bottom half). Selected step-size is marked with a star.
22
P-values for the Null Hypothesis
No Path Optimal Path No Path Optimal Path
p 0.05 (significant) p 0.05 (significant)
p > 0.05 (not significant) p > 0.05 (not significant)
Network Size (Optimal Path)
0.49 1.00 1.00 1.00 0.09 0.99 1.00 1.00
3x32 3x16 3x8 3x4 2x32 2x16 2x8 2x4
0.00 0.00 0.75 0.47 0.99
16
Capacity (Optimal Path)
0.46 1.00 1.00 0.03 1.00 1.00
0.00 0.43 0.19 0.90
64
0.02 0.88 0.01 0.47
0.03 0.03
256
0.00 0.00 0.00
1.00 1.00 1.00 0.14 0.99 1.00 1.00
1.00 1.00 0.07 1.00 1.00
400
0.00 0.00
0.71 0.00 0.18
576
0.00 0.02
16 64 256 400 576 2x4 2x8 2x16 2x32 3x4 3x8 3x16 3x32
Capacity (No Path) Network Size (No Path)
Figure 11: Experiment 1. Significance Tests. Let Pi and Pj be the performances associated with capacities of the row and column. The plot should be read row-wise: when the (i, j)-cell is green, Pi is significantly higher than Pj .
B.5 Experiment 2. Learning in the Presence of Other Fixed Artifacts
10000
8000
Total Reward
6000
4000 No Path
Random Path
Landmarks
2000 Misleading Path
Suboptimal Path
Optimal Path
0
0 16 64 144 256 400 576
Capacity
Figure 12: Capacity vs performance of Linear-Q in the presence of fixed artifacts. Total reward for each artifact type is shown. Each data point presents an average and standard-error from 30 seeds. Capacity ranges from 12 to 242 (1 to 576).
23
Figure 13: Environments considered in Experiment 2.: Random (top left), Misleading (top right), Suboptimal (bottom left), Landmarks (bottom right).
24
Setting Capacity 16 64 256 400 576 No Path 183.83 ± 17.58 1920.57 ± 279.08 6841.67 ± 452.31 6434.30 ± 343.49 7783.67 ± 401.12 Optimal 6466.93 ± 335.23 6969.20 ± 500.31 9696.77 ± 151.79 9272.03 ± 200.73 9514.20 ± 196.36 Suboptimal 553.07 ± 141.01 2654.80 ± 318.64 8895.57 ± 248.11 8873.90 ± 377.40 9257.97 ± 333.89 Misleading 334.70 ± 96.58 3134.10 ± 470.17 7346.07 ± 563.83 9142.63 ± 245.85 9552.57 ± 125.48 Random 146.13 ± 22.29 3900.10 ± 519.15 8292.07 ± 421.55 8101.60 ± 346.66 9004.53 ± 296.00 Landmarks 193.30 ± 18.24 2367.57 ± 365.12 7656.87 ± 381.39 7474.90 ± 455.72 8509.37 ± 338.39 Dynamic 250.13 ± 25.96 2029.00 ± 246.35 7599.07 ± 284.03 7639.03 ± 159.47 8085.03 ± 127.03
Setting Depth Width 4 8 16 32 2 406.47 ± 178.31 1803.20 ± 326.55 3733.50 ± 162.14 4354.73 ± 41.32 No Path 3 219.03 ± 4.00 1097.90 ± 244.10 3657.53 ± 182.99 4178.57 ± 133.47 2 413.80 ± 146.60 1845.80 ± 307.89 4191.47 ± 134.28 4441.77 ± 21.80 Optimal 3 374.53 ± 142.99 1666.07 ± 301.86 4313.17 ± 60.00 4473.87 ± 23.60 2 391.00 ± 167.85 2040.43 ± 332.12 4068.40 ± 153.21 4402.13 ± 25.39 Suboptimal 3 225.37 ± 68.80 1461.40 ± 317.94 3836.13 ± 210.88 4396.17 ± 20.86 2 524.77 ± 194.58 2220.50 ± 329.63 4205.07 ± 54.02 4470.10 ± 17.02 Misleading 3 413.23 ± 153.92 1408.50 ± 300.97 3970.07 ± 182.72 4445.97 ± 13.94 2 330.07 ± 147.84 2012.10 ± 306.82 4080.00 ± 98.73 4406.73 ± 22.54 Random 3 272.23 ± 103.04 1341.30 ± 292.98 3632.83 ± 220.15 4293.20 ± 20.12 2 481.77 ± 201.62 1840.67 ± 330.88 4028.80 ± 158.04 4397.70 ± 36.26 Landmarks 3 214.43 ± 65.62 1263.70 ± 301.42 3833.50 ± 212.56 4369.50 ± 42.72
Table 1: Average total reward with standard errors over thirty independent seeds, for all settings considered. Bold text indicates satisfaction of our empirical condition.
25
10000 Random Path 10000 Misleading Path
Capacity Capacity
7500 16 7500 16
Total Reward
Total Reward
64 64
256 256
5000 400 5000 400
576 576
2500 2500
0 0
4
8
02
04
08
2
4
4
8
02
04
08
2
4
00
00
0.0
0.0
00
00
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Step-size Step-size
10000 Suboptimal Path 10000 Landmarks
Capacity Capacity
7500 16 7500 16
Total Reward
Total Reward
64 64
256 256
5000 400 5000 400
576 576
2500 2500
0 0
4
8
02
04
08
2
4
4
8
02
04
08
2
4
00
00
0.0
0.0
00
00
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Step-size Step-size
5500 Random Path 5500 Misleading Path
2x4 2x4
4125 2x8 4125 2x8
Total Reward
Total Reward
2x16 2x16
2x32 2x32
2750 3x4 2750 3x4
3x8 3x8
1375 3x16 1375 3x16
3x32 3x32
0 0
-05
-05
1
5
01
05
1
-05
-05
1
5
01
05
1
00
00
0.0
00
00
0.0
0.0
0.0
0.0
0.0
1e
5e
1e
5e
0.0
0.0
0.0
0.0
Step-size Step-size
5500 Suboptimal Path 5500 Landmarks
2x4 2x4
4125 2x8 4125 2x8
Total Reward
Total Reward
2x16 2x16
2x32 2x32
2750 3x4 2750 3x4
3x8 3x8
1375 3x16 1375 3x16
3x32 3x32
0 0
-05
-05
1
5
01
05
1
-05
-05
1
5
01
05
1
00
00
0.0
00
00
0.0
0.0
0.0
0.0
0.0
1e
5e
1e
5e
0.0
0.0
0.0
0.0
Step-size Step-size
Figure 14: Experiment 2. Step-size sweeps. Linear Q-learning (top half), DQN (lower half).
26
0.05 Random Path 0.05 Misleading Path
Capacity Capacity
0.04 16 0.04 16
Average Reward
Average Reward
64 64
0.03 256 0.03 256
400 400
576 576
0.02 0.02
0.01 0.01
0.000 50 100 150 200 0.000 50 100 150 200
Time Step (x 103) Time Step (x 103)
0.05 Suboptimal Path 0.05 Landmarks
Capacity Capacity
0.04 16 0.04 16
Average Reward
Average Reward
64 64
0.03 256 0.03 256
400 400
576 576
0.02 0.02
0.01 0.01
0.000 50 100 150 200 0.000 50 100 150 200
Time Step (x 103) Time Step (x 103)
0.05 Network Size Random Path 0.05 Network Size Misleading Path
2x4 2x4
2x8 2x8
0.04 2x16 0.04 2x16
Average Reward
Average Reward
2x32 2x32
3x4 3x4
0.03 3x8 0.03 3x8
3x16 3x16
3x32 3x32
0.02 0.02
0.01 0.01
0.000 25 50 75 100 0.000 25 50 75 100
Time Step (x 103) Time Step (x 103)
0.05 Network Size Suboptimal Path 0.05 Network Size Landmarks
2x4 2x4
2x8 2x8
0.04 2x16 0.04 2x16
Average Reward
Average Reward
2x32 2x32
3x4 3x4
0.03 3x8 0.03 3x8
3x16 3x16
3x32
0.02 3x32 0.02
0.01 0.01
0.000 25 50 75 100 0.000 25 50 75 100
Time Step (x 103) Time Step (x 103)
Figure 15: Experiment 2. Average Reward. Linear-Q (top half), DQN (bottom half).
27
P-values for the Null Hypothesis P-values for the Null Hypothesis
No Path Random Path No Path Misleading Path
p 0.05 (significant) p 0.05 (significant)
p > 0.05 (not significant) p > 0.05 (not significant)
Capacity (Misleading Path)
0.91 1.00 1.00 1.00 1.00 0.06 1.00 1.00 1.00 1.00
16
16
Capacity (Random Path)
0.00 1.00 1.00 1.00 0.02 1.00 1.00 1.00
64
64
256
256
0.01 0.00 0.19 0.24 0.09 0.74
400
400
0.00 0.28 0.00 0.00
576
576
0.01 0.00
16 64 256 400 576 16 64 256 400 576
Capacity (No Path) Capacity (No Path)
P-values for the Null Hypothesis P-values for the Null Hypothesis
No Path Suboptimal Path No Path Landmarks
p 0.05 (significant) p 0.05 (significant)
p > 0.05 (not significant) p > 0.05 (not significant)
Capacity (Suboptimal Path)
0.01 1.00 1.00 1.00 1.00 0.35 1.00 1.00 1.00 1.00
16
16
Capacity (Landmarks)
0.04 1.00 1.00 1.00 0.17 1.00 1.00 1.00
64
64
256
256
0.00 0.00 0.01 0.09 0.01 0.59
400
400
0.00 0.03 0.04 0.69
576
576
0.00 0.09
16 64 256 400 576 16 64 256 400 576
Capacity (No Path) Capacity (No Path)
Figure 16: Experiment 2. Linear Significant Tests. Let Pi and Pj be the performances associated with capacities of the row and column. The plot should be read row-wise: when the (i, j)-cell is green, Pi is significantly higher than Pj .
28
No Path Random Path No Path Misleading Path
p 0.05 (significant) p 0.05 (significant)
p > 0.05 (not significant) p > 0.05 (not significant)
Network Size (Misleading Path)
Network Size (Random Path) 0.63 1.00 1.00 1.00 0.23 1.00 1.00 1.00 0.33 1.00 1.00 1.00 0.06 0.96 1.00 1.00 3x32 3x16 3x8 3x4 2x32 2x16 2x8 2x4
3x32 3x16 3x8 3x4 2x32 2x16 2x8 2x4
0.32 1.00 1.00 0.01 1.00 1.00 0.19 1.00 1.00 0.00 1.00 1.00
0.04 0.99 0.02 0.72 0.00 0.98 0.00 0.43
0.14 0.05 0.01 0.02
1.00 1.00 1.00 0.30 1.00 1.00 1.00 1.00 1.00 1.00 0.11 0.99 1.00 1.00
1.00 1.00 0.26 1.00 1.00 1.00 1.00 0.21 1.00 1.00
1.00 0.53 0.98 0.98 0.12 0.82
0.20 0.03
2x4 2x8 2x16 2x32 3x4 3x8 3x16 3x32 2x4 2x8 2x16 2x32 3x4 3x8 3x16 3x32
Network Size (No Path) Network Size (No Path)
No Path Suboptimal Path No Path Landmarks
p 0.05 (significant) p 0.05 (significant)
p > 0.05 (not significant) p > 0.05 (not significant)
Network Size (Suboptimal Path)
0.53 1.00 1.00 1.00 0.15 0.99 1.00 1.00 0.39 1.00 1.00 1.00 0.10 0.97 1.00 1.00
3x32 3x16 3x8 3x4 2x32 2x16 2x8 2x4
3x32 3x16 3x8 3x4 2x32 2x16 2x8 2x4
Network Size (Landmarks)
0.31 1.00 1.00 0.01 1.00 1.00 0.47 1.00 1.00 0.04 1.00 1.00
0.07 0.96 0.05 0.71 0.10 0.97 0.07 0.76
0.17 0.05 0.22 0.06
1.00 1.00 1.00 0.46 1.00 1.00 1.00 1.00 1.00 1.00 0.53 1.00 1.00 1.00
1.00 1.00 0.18 1.00 1.00 1.00 1.00 0.34 1.00 1.00
0.99 0.26 0.91 0.99 0.27 0.91
0.06 0.09
2x4 2x8 2x16 2x32 3x4 3x8 3x16 3x32 2x4 2x8 2x16 2x32 3x4 3x8 3x16 3x32
Network Size (No Path) Network Size (No Path)
Figure 17: Experiment 2. DQN Significant Tests. Let Pi and Pj be the performances associated
with capacities of the row and column. The plot should be read row-wise: when the (i, j)-cell is
green, Pi is significantly higher than Pj .
B.6 Experiment 3. Learning in the Presence of a Dynamic Path
29
Dynamic 0.05 Dynamic
10000 Capacity
Capacity
16 0.04 16
7500
Average Reward
64
Total Reward
64
256 0.03 256
5000 400 400
576
576 0.02
2500
0.01
0
4
8
02
04
08
2
4
0.000
00
00
0.0
0.0
0.0
0.0
0.0
50 100 150 200
0.0
0.0
Step-size Time Step (x 103)
Figure 18: Experiment 3. Dynamic Path Average Reward and Step-size sweeps. Linear-Q.
P-values for the Null Hypothesis
No Path Dynamic Path
p 0.05 (significant)
p > 0.05 (not significant)
0.02 1.00 1.00 1.00 1.00
16
Capacity (Dynamic Path)
0.39 1.00 1.00 1.00
64
256
0.08 0.01 0.65
400
0.00 0.63
576
0.24
16 64 256 400 576
Capacity (No Path)
Figure 19: Experiment 3. Linear Significance Tests. Let Pi and Pj be the performances associated with capacities of the row and column. The plot should be read row-wise: when the (i, j)-cell is green, Pi is significantly higher than Pj .
30