Partially Observable Reinforcement Learning with Memory Traces
Authors: Onno Eberhard
Michael Muehlebach
Claire Vernade
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement learning theory
Partial observability
Memory
Primary area: theory->reinforcement_learning_and_planning
TL;DR: Eligibility traces are more effective than sliding windows as a memory mechanism for RL in POMDPs.

Abstract: Partially observable environments present a considerable computational challenge in reinforcement learning due to the need to consider long histories. Learning with a finite window of observations quickly becomes intractable as the window length grows. In this work, we introduce *memory traces*. Inspired by eligibility traces, these are compact representations of the history of observations in the form of exponential moving averages. We prove sample complexity bounds for the problem of offline on-policy evaluation that quantify the return errors achieved with memory traces for the class of Lipschitz continuous value estimates. We establish a close connection to the window approach, and demonstrate that, in certain environments, learning with memory traces is significantly more sample efficient. Finally, we underline the effectiveness of memory traces empirically in online reinforcement learning experiments for both value prediction and control.

Partially Observable Reinforcement Learning with Memory Traces
Onno Eberhard
Michael Muehlebach' Claire Vernade
Abstract
new memory
old memory
new observation
Partially observable environments present a con- siderable computational challenge in reinforce- ment learning due the need to consider long his- tories. Learning with finite window of observa- tions quickly becomes intractable the window length grows. In this work, we introduce memory traces. Inspired by eligibility traces, these are compact representations of the history of observa- tions in the form of exponential moving averages. We prove sample complexity bounds for the prob- lem of offline on-policy evaluation that quantify the return errors achieved with memory traces for the class of Lipschitz continuous value esti- mates. We establish close connection to the window approach, and demonstrate that, in cer- tain environments, learning with memory traces is significantly more sample efficient. Finally, we underline the effectiveness of memory traces empirically in online reinforcement learning ex- periments for both value prediction and control.
Memory update:
+ (1
X)
+
Memory traces during trajectory (A 0.8):
Figure 1. Illustration of the memory trace mechanism in the T-maze environment. The agent starts in the leftmost tile and receives an observation that reveals if the reward at the end of the corridor is at the top or bottom. The agent has to remember this information until the last step. It can be seen that this information has faded in zs (the final memory trace), but has not completely disappeared.
ods based on recurrent neural networks that learn directly from the stream of observations (e.g., Ni et al., 2022), this feature-based approach provides an analysis framework that is mathematically tractable.
The archetypical feature in partially observable reinforce- ment learning (RL) is the length-m window, which truncates the history and only keeps the m most recent observations. In deep RL, this approach is known as frame stacking (Mnih et al., 2015). Under certain assumptions, such as observabil- ity (Golowich et al., 2023; Liu et al., 2022) or multi-step decodability (Efroni et al., 2022), it can be shown that such a window is sufficient for good behavior. However, many settings, the window would have to be very long to be useful, which problematic, as the complexity of learning general functions of length-m windows scales exponentially in m. To address this issue, this paper introduces different fea- ture that we call the memory trace. This feature is inspired by eligibility traces, and consists of an exponential moving average of the stream of observations. Thus, upon receiving a new observation y/, the memory trace 2, is moved closer toward ye:
1. Introduction
Learning and acting in partially observable environments requires memory. generally not enough to act simply according to the most recent observation, and an agent must therefore keep track of the past, as every piece of informa- tion is likely to be relevant for future actions. In the absence of additional assumptions, optimal behavior requires the agent to reason over its entire history of observations. This space quickly becomes intractable, and just like with contin- uous state spaces in fully observed systems, is therefore necessary to resort to approximation. This article inves- tigates the fundamental limitations and trade-offs arising from these approximations. We focus on extracting features from the history of observations and analyze the complexity of learning functions of these features. In contrast to meth-
21 Aa + (1 A)yt.
(I)
Max Planck Institute for Intelligent Systems, Tübingen, Ger- many University Tübingen. Correspondence to: Onno Eber- hard <oeberhard@ tue mpg.de>>.
where À E [0, 1) is forgetting factor. This mechanism is illustrated in Fig. 1 in the T-maze environment (Bakker, 2001), where we took inspiration from Allen et al. (2024).
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Our results are concerned with the problem of offline on-policy evaluation, which is an ideal setting for studying

---

Partially Observable Reinforcement Learning with Memory Traces
the window and memory trace features in terms of sample efficiency. We find that learning with windows is equivalent, in terms of capacity and sample complexity, to learning Lip- schitz continuous functions of memory traces if and only if A < 3. For larger X, we demonstrate that there are environ- ments where learning Lipschitz functions of memory traces is significantly more efficient than learning with windows to achieve a desired return error. In particular, we show that the T-maze (Fig. 1) is such environment and also present an illustrative two-state environment to provide intuition.
action space is U {ut ..... u J, and the observation space is y fy',..... ...., ,yli) c 2, where 2 is Fuclidean space. For example, if y is one-hot, then y' is the et stan- dard basis vector of R = 2. The POMDP is described by the transition dynamics p(1++1 Iee ut), the emission prob- abilities p(y: zz), and the initial state distribution p(æo). The reward function r : y + [r, r] maps observations to rewards." ! If policy is fixed, then the POMDP reduces to a hidden Markov model (HMM).
Memory traces and windows. A HMM's history at time t is the sequence of observations up to that time: h4 = (ye, Ut-1....) ). It is often convenient to let the time t = 0 stand for the current time step and write h = hgg and y - yoo A history h E ylAl may be of finite or infinite length |h| E {0, I,..., 0o}. The length-m window is obtained from a history by truncation:
Turning to online reinforcement learning, we show that memory traces are easily incorporated into existing algo- rithms to provide a scalable alternative to windows. We empirically demonstrate that, under temporal difference learning with linear function approximation, memory traces significantly outperform the general length-m window ap- proach in simple random walk experiment. Finally, we show that memory traces can handle considerably longer memory requirements than the frame stacking approach by evaluating& a proximal policy optimization (PPO; Schulman et al., 2017) agent in the T-maze environment.
winm (h) = (Jo, y/1...... 8-m+1)-
The memory trace corresponding to history h is defined as
1-1
xx(h) = A1
Σ
X y-k
(2)
2. Related work
The topic of memory has a Soagdstan history in rein- forcement learning. Over the years, there have been many proposals for how to design effective memory, from will distinction memory (MeCallum, 1993), which, recognizing that not all length-m histories are important, builds tree of histories that are useful for value prediction, to neural Tur- ing machines (Graves et al., 4), in which deep learning agent is equipped with external memory to write to and read from. Common types of memory for deep reinforcement learning include recurrent neural networks (e.g.. Hausknecht & Stone, 2015) and transformer architectures (e.g., Esslinger et al., 2022). While some of these designs have lead to em- pirical success (c.g., Vinyals al., 2019), the only type of memory that is theoretically well understood is the length-m window, which has been studied extensively (Efroni et al., 2022; Golowich et al., 2023; Cayci et al., 2024).
Given a history h, we often write 2, = 2 (he), and define
= - Zy. We can then rewrite (2) recursively as to obtain (1)
for L E (o..... - |M + 1), with 2-|n] = 0. The set of all length-m memory traces defined as
2 = (zx(b) h ym
where m 1, ). and we define 2, - 2 Both windows and memory traces can be extended to include past actions in addition to observations.
Covering numbers. Many of our results are based on the concept of covering numbers. Let (X, p) be a metric space and T C X. A finite set S C X is said to e-cover T. for some e 0, if for every x E T, there exists a y E S such that p(x, y) S é. The e-covering number (T) is the cardinality of the smallest e-cover of T. The metric entropy of T is defined as HT) = log N. (T), and the Minkowski dimension of T is defined as dim(T'- = lim_- log 1/e as- suming the limit exists. We deal with both Euclidean spaces, in which case p is the Euclidean norm, and functional spaces, where p is the sup-norm I| = sup,, (x)).
The memory trace that we present in this work is inspired by the eligibility trace (e.g.. Sutton& & Barto, 2018, Chapter 12), which can also be interpreted as type of memory. The relevance of eligibility traces for learning in partially observable environments has been studied before (Loch & Singh, 1998; Allen et al., 2024), but they have, to the best of our knowledge, not been analyzed as a memory for RL.
(T)
Offline on-policy evaluation. We study the problem of offline on-policy evaluation. This setting assumes the avail- ability of a dataset D- = {Ti)i= consisting of n trajectories
3. Preliminaries
= (..., U- 1- No: V/ 1/2 .); ~ E
POMDPs. We consider the problems of prediction and control in finite partially observable Markov decision pro- cess (POMDP). The state space is X {x² ...., [ J. the
Sometimes is defined to map from X x U. Our definition is equivalent (since it is always possible to extend y to include rewards) and emphasizes that rewards are observed quantities.
2

---

Partially Observable Reinforcement Learning with Memory Traces
Fast forgetting (A 0.3)
Critical forgetting 0.5)
Slow forgetting (A 0.7)
23)/v/6
0.6
A
History length m
0.2
4
-2
0.0
(251
-0.4
4
-0.5
0.0
0.5
0.5
0.0
0.5
0.5
0.0
0.5
(z2 za)/v2
(22 22
( 23) /
Figure 2. visualization of macc space, where y is one-hot with [9] = 3. The memory traces form Sierpiniski triangle patterns, with À controlling the dilation between triangles. The center point of each triangle corresponds to the length-m window shared by all traces that make up the triangle. A similar visualization of the trace space one-hot observations with | 4 shown in Fig.
that are drawn independently from an environment (a hidden Markov model with a reward function r). We assume that all trajectories are of infinite length in both positive and negative time, and consider the problem of approximating the value function you - [u, 5).
2x) and (h) are only equal if their difference is zero:
(h) 2사 (h)
Σ
> F-k)
Σ (,()))'
1
A==
where we have defined, using the Iverson bracket [:].
(h) = E&
Σ
('r(11-1) ho h m 1=0
as (;(A) = Σ (Lv+ - = =f)).
(3)
k=
where y 13/(1-))
f/(1 and 7 E 10, a discount factor. Given a function class I {f : y [e, o]}, our goal is find the function f F that minimizes the return error
As y is linearly independent, the difference 2 (h) 22 (h) is only zero if (A( for all i. By assumption, the histories are distinct, and therefore there must be at least one a with at least one nonzero coefficient. By (3), the highest-order coefficient of this ag (which exists because the histories are finite) is thus either +1 or 11 We will now show that if À E Q 2, then ax (A) / O, completing the proof. Assume, for the sake of contradiction, that there exists X = ". with p and q coprime integers, such that (A(A) 0. Then, by the rational root theorem (e.g., Aluffi, 2021, Prop. 7.29), must divide However, as c E {-1, +1}. it follows that E {-1, +1}. and so À is an integer. Thus, we can conclude that (A) + and hence 2 (h) * 2x')..
Ne (f) = 1e (f Σ Er((0+)))
As this expectation cannot be computed directly, we instead consider functions that minimize the empirical return error
(,) = 1 Σ E((0..B-1.... 2n
r((M))))
TED
L=
which we analyze via generalization bounds.
In Appendix A, we show with two counterexamples that injectivity is not guaranteed if À is irrational, or if the his- tories are of infinite length. We also show that the result can be extended to linearly dependent observation spaces (Theorem A.3), in which case the set of À that guarantee injectivity is potentially more complex, but is still dense in (0, 1).
4. The geometry of trace space
Perhaps surprisingly, it turns out that, under mild conditions, the memory trace preserves all information of the history.
Theorem 4.1 (Finite injectivity). If E (0, 1)n Q and y is linearly independent, then the memory truce is injective: if
Injectivity of Σ사 implies that the complete history h can be perfectly reconstructed from the memory trace vector z (h). Thus, the memory trace is an equivalent representation of the history. However, the exponential decay of (2) imparts additional structure on the space of memory traces, which
and h are distinct finite histories, then 2 (h) * 2x (h).
Proof. Although the histories h and h are finite, we can 0- pad them by defining y-k for 2 |h| and 7-x = 0 for 2 !h| (the memory trace is unaffected by this). The traces
3

---

Partially Observable Reinforcement Learning with Memory Traces
makes them attractive representations for learning. We now briefly investigate this structure, and in the following sec- tions we analyze the efficiency of learning with memory traces compared to window- hindow-based learning.
Lemma 4.4. If is one-hot, then the Minkowski dimension of 2x is, for all X 2.
log 181 = d2-
dim(Z,)
(1/(1/A)
If y is one-hot, then all memory traces = E 2 lie in a (II) 1)-dimensional affine subset of [o, 1|101, as can be
For all X E [0, we have dim(2x) min - dx Proof. See Appendix B.
verified by summing over the elements of E xx
M9| =
m
5. Complexity of offline on-policy evaluation
x)
(y- =1 A.. (4)
We now analyze the sample complexity of offline on-policy evaluation. Throughout this section, we assume that y is one-hot. We are interested in the following two families of function classes: length-m window-bass based functions
A=
In Fig. 2, the sets 2 for y = 3 are visualized by orthogo- nal projection onto this two-dimensional subset. It can be seen that the distance between traces greatly depends on A. This can be quantified as follows.
Fm = {f winm y o],
and L-Lipschitz continuous functions in trace space
Lemma 4.2 (Concentration). Lei and h be two histories of one-hot observations such that winm (h) = winm (h) for some m. Then, the corresponding traces satisfy
F = (f 2 2x + [v. E). is L-Lipschitz).
How well a function class I is suited for learning the value function in an environment & depends on the minimum achievable return error (²) = inf ser (f) and on the size of the function class, measured by the metric entropy HT). This is expressed by the following result.
(h) 2x(1l & V2x".
Proof. See Appendix B.
LI
Intuitively, this results states that it is hard to distinguish between traces that only differ in observations from the far past. While Theorem 4.1 guarantees the existence of functions that map traces to arbitrarily chosen values, the concentration result shows that these functions may have very large Lipschitz constants. In particular, when two traces 2 and y correspond to histories that share the last m observations, the function f needs to have a Lipschitz constant of least [f() - f())l/( (12)1/(22m)) to map these traces to two different values (=) and f()).
Theorem 5.1 (Hoeffding bound). Given dataset o tra- jectories from an environment E, function class T, and some > O, let 3 be the smallest c-cover of I and fr. = arg miinness Ru (f). Then, with probability at least 1 - 8.
H. + log
62 2
Re < (F) (F)+ 22V A2
E
2n
where we have defined A = ū
Proof. This result combines standard generalization bound from statistical learning theory that applies Ho- effding's inequality to a finite hypothesis class F with Lemma 5.2 (below). The full proof is in Appendix B. O
Lemma 4.2 only gives an upper bound on the distance be- tween traces. For guarantee that a given Lipschitz constant is sufficient, we need lower bound on this distance. This is the subject of the following result.
Lemma 5.2. Let & be an environment, F a function class,
Lemma 4.3 (Separation). Let h and h be two histories of one-hot observations such that winm (h) * win. (h) for some m. Then, if X S 2' the corresponding traces satisfy
and > 0. IfS is an e-cover of then
2
Re (S) RR cA
2
(h) - 2x(1)| 2 V2(1 2
Proof. See Appendix B.
While the Hoeffding bound above does not guarantee that function classes with large metric entropy are less suitable for learning, it suggests that good value function is more easily learned if H., (F) is small. The focus on metric en- tropy measure for the complexity of hypothesis classes is well established in statistical learning theory (Wainwright, 2019; Haussler, 1992; Allard & Bölcskei, 2024). We will now analyze the metric entropies of the classes Fm, and FA,L, and compare their return errors across different envi- ronments. We begin by computing the metric entropies.
Proof. See Appendix B.
This result shows that, if < J. then Nλ is injective even for infinite histories and irrational X. Figure 2 illustrates why the condition X < is necessary: for larger X, the traces move past each other and may overlap.
The set 2, has a fractal nature that can be described through its Minkowski dimension, which helps characterize the sam- ple complexity of learning with memory traces.
4

---

Partially Observable Reinforcement Learning with Memory Traces
Lemma 5.3. Let m E No be window length. The metric entropy of F'm is, for all 0,
and h E yo such that = (x( (this history exists by definition of 2x). Let 2 = 2x =wiiiim (h)) E St. Then,
A
(T) = 1/ log
2 S (1 - A)
2e
k=m
Thus, function of m, He(F E )())
log(2L/e) e
n < exp
log A
U Lemma 5.4. Let X E 1) and > 0 be a Lipschitz constant. The metric entropy of x satisfies, for all > 0,
Proof. See Appendix B.
log(1/A)
2T.
proving that S is an 2T. cover. The cardinality of S is
|Sa| 1/
H. S log
A
19
2L dx
and
log(2L/e) (1g(1/A)
+1)} 2L dx
S exp log |9]
|
[A]
22 [
18
H.(F.,.) & log
The first result then follows from (5).
For the second inequality, we construct a different set S2 C [0, 1j19). Let ep = V 1, and extend eo to an orthonormal basis en, 61.... ........1yy11 of RM We now define
Thus, a function of X and L, the metric entropy satisfies
(F E 2 (m (.mi((xx18111111))
Proof. L 0, X E [0. 1), and L O. We will construct two different e-covers of Fx,r. to establish the two upper bounds. The difference between these two is how the (infi- nite) set ZA is approximated. S C [0, 1| be a finite set that 2z -overrs ZA (in the Euclidean norm). Then, for each E 2., there exists a u=(2) E S such that w=])))) S 21- We will now show that the set (S) + {f o w Z f
191-1
ce (1,..,, G91-1 E Co...
S2 y
eo +
where 8 =
211-191-- and where Gg is a finite set of [1/6]
points in [- that 8-covers this interval. Such set Gs
c
exists by the argument presented in the proof of Lemma 5.3: taking [1/8] uniformly spaced points with equal distance 28 as the centers of 8-balls, a volume of (265 2 8-covered, which is enough cover [-1,
S - V3} e-covers Fx,r. (in the sup-norm), where V. is set of [2)) points in [g, 5) that e-covers this interval (see proof of Lemma 5.3). Let f E Fx.L- Then, there exists ūj such that f = fo zx. Kirszbraun's 's theorem (e.g.. Federer, 2014, Theorem 2.10.43) tells us that the L-Lipschitz function f can be ex- tended to L--Lipshitz function f [0, 1|18| + [u. o] with the property that flz,- = For every E S, define g(s) e V; such that lØ(s) - [(+)] < 5. This is possible because Vg is an 5-cover of je, E). Now, define g (S) as g = I zx. Then, for all histories h E yo,, with z = (x),,
an T--Lipschitz function ʃ Z,x + [e,
We now show that S2 is 2L- -cver of Zx. Let 2 E Zx. Then, using (4), we have ||||| S ||=|| Σ. 2 = 1. This
implies that 2 Tee E [-1,1] for all é E {O....,I' - 1}.
Thus, for each i, there exists a point k; E Gs such that Iz e, ---hi k2 S 6. Now, define w E S2 as
19 Σ
1 v
60
kee
-(h)) (f(h) - 9(h))= = 1f(2) - g(w(2))
From (4), we have = _ eg
Thus.
V
< [f()) - f(w(2))) + -=((ww))) - g(w(3))
y| 1 Σ x Te k.)eell
s [| (0)2)|| + c/2 cc
||
w|| =
i=1
Thus, the metric entropy of Xx satisfies
|91 1
1 kil?
H.( s log (S) |S] log [Vgl = |S| log A/c].
(5)
1=1
To get the first inequality, we define the set S1 C [0, 1]181 as the following set of length-m memory traces:
I (1 - 1)0² =
2
2L
Hence, S2 2τ. -coeers Zy. The cardinality of Sz is
5 = (h) E ymm where m [og((2/e)
log(1/A)
2T |
-1-1
| = 1G1= 1811
with (+)+ = max(0, -).
We first show that S1 2L covers Z,, and then compute the cardinality of Sj. Let 2 E Z,
and the result follows from (5).
5

---

Partially Observable Reinforcement Learning with Memory Traces
These expressions are difficult to compare without addi- tional context. In the following two sections we show that the efficiency of learning with windows and memory traces, according to Theorem 5.1 and our metric entropy upper bounds, is equivalent for À < ("fast forgetting"), while memory traces can be significantly more efficient when ("slow forgetting").
log y = c| exp log(1/A) 1) 1og(1/A)
c|ylT E ((
The next result is similar in spirit, as it shows that for every À and Lipschitz constant L there exists a window length m such that Fm has a return error comparable to Fx.L- but it does not go quite as far in terms of complexity. In the next section we show why: there are environments where memory traces are significantly more efficient than windows.
A 12
5.1. Fast forgetting: À <
Our first result states that, if there is a window length m such that Fm achieves a certain return error at the cost a certain complexity (measured by the metric entropy), then there is X and I Lipschitz constant T, 0 such that Fx, achieves the same return error and the same complexity, up to constant factors. Thus, there exists no environment where windows outperform memory traces in general.
Theorem 5.6 (Trace to window). For every E (0,1), Lips- chitz constant O, and c E (0, L), there exists a window length m(X, L) No such that, for every environment e,
Rg (F S (F cA ? 2
Theorem 5.5 (Window to trace). For every window length m E N and every À < 2, there exists a Lipschitz constant ((m) > O such that, for every E > 0 and every environment E,
and, taking He (fm().)) as a function of X and L,
He (m((())))) E =((L.).
Re (())) S (Fm) and, taking He (Fx, as a function of m,
Proof. Let A E [0, 1). L > O, and e E (0, L). Define m(X, L) as
[og(T./()
He (T) E O(1)IT) = (fm))
m
log(1/A)
Proof. Let m E N and xe E [0, f). Define L(m)
We begin by showing that for every f Fx,L, there ex- ists a gg E Fm such that ||ʃ glo> 6. The return er- ror bound then follows from Lemma 5.2. Let f E Fx,L- Then, there exists an L-Lipschitz function f Zx + [w. ø] such that f = f o 2x. As in Lemma 5.4, we can use Kirszbraun's 's theorem to extend f to an L-Lipschitz function f : [0. 1] | - [e, ō] with the property that flz, 2, f. Now define g = f o 2x winm E Fm. Let h y be history, and define = (h) and nd = zx (win (h)). From the proof of Lemma 5.4, we know that || - 2" Am < G.
A
= 22(1 21)2m-1'
We begin by showing that Fm C FxL, implying that Rg (Fx,z) < Rgg (Fm) for any environment E. Let Fm.
Since x < 2. Lemma 4.3 guarantees that 2 is invertible, and we can define g 2A - [c, u] as g = f We now show that g is L-Lipschitz, implying that f 20 Fx,L- The Lipschitz constant of g is the supremum of the Lipschitz ratio:
Thus,
[g(2) - 93)
Lip(g) = sup 2.5E 2
(f (hh) = f(=")) S L12 - zzd S SE.
||z -
The metric entropy of Fm satisfies (Lemma 5.3)
Let 2 # E Z, and define = (2) and h = 2 (2). If winm (h) winm(h) then g(2) g(3). making the Lipschitz ratio 0 < L. Otherwise, if win, (h) A winm (h), Lemma 4.3 guarantees that ||2 I|| > /2(1 1
(fmm) = -11 log
2
+1 +1)} log 2e [og(1/A)
log(L/c)
S exp log |
As 19(z) ((3) < A, we have Lip(g) S L, showing that fE Fx,..
1
(
T.
d2
= log
|
E O(L))
Given e > O, the metric entropy satisfies (by Lemma 5.4)
2
V2A
da
H.(F).)) < log
|
While we also know that (Fx, E ((T4)), this is not lower bound. In fact, Lemma 5.4 gives us a second up- per bound, (F...) E (( In the fast forgetting regime (A < 1). this second bound is not relevant, as the following lemma shows.
(1
A
V2A
da
1
(m-1)ds
= =log
1yl
(1 2AJE
6

---

Partially Observable Reinforcement Learning with Memory Traces
Lemma 5.7. Let [ > 1. IfA 3. then d2 < |
p
hg
1110)
Optimal for length-4 histories
0.6
0.2
0.6
0.8
Proof. See Appendix B.
Thus, X < 2. learning with windows is cquivalent to learn- ing with memory traces, as far as our results go. However, show next, in the slow forgetting regime (A 2 2), memory traces be significantly more efficient.
Error probability
0.4
0.2
5.2. Slow forgetting: X 2
0.3
0.3 Transition probability p
Transition probability p
When A 2 1.2 we lose the guarantee of separation (Lemma 4.3), memory traces be arbitrarily close together. However, not all histories are necessarily relevant for accurately representing value function. The following result constructs an environment where most histories are irrelevant. A large À can push the traces that do matter apart (see Lemma 4.2), such that a smaller Lipschitz constant suffices for estimating the value function.
Figure 3. Investigating simple 2-state HMM. (Left) The most recent observation is O, but depending on the parameters and of the HMM, the predicted state may he either or 1. (Right) The choice of À depends on the properties of the HMM.
recent observation may be misleading. Instead, a more reli- able estimate of the state can be obtained by accumulating several observations. On the other hand, if p is large, then one should not rely too much on older observations, as these are likely outdated. In the left of Fig. 3, we show how the state estimate changes based on these parameters.
Theorem 5.8 (T-maze). There exists sequence (Ex) of environments (with constant observation space Y) with the property that, for every e O,
min (Fm) mEN
Re, (Fm) 0} ((()))), and
Given a reward function т, we would like to approximate the value function v(h) with Lipschitz function f E Fx.L. The optimal choice for À may be defined
min min (FA.L) RR, (f 0} e O(k -1 (E(0,1) 1.0
Proof. The T-maze environment with corridor length l (see Fig. 1) provides such sequence. As the first tile has to be remembered until the end of the corridor, the window size must be at least m = kr which yields the first line (using Lemma 5.3). Setting À ا-ع we show that a Lipschitz constant of I, = 22k suffices to solve this task with zero return error. The second line then follows from Lemma 5,4. The complete proof is deferred to Appendix B.
arg min inf {L 2 Rg (Fx.)) = 0). XE(O.1)
where, for this simple environment, the choice of does not influence the result. In the right of Fig. 3, we numerically approximate X while restricting the computation of the return error to only consider length-4 histories. We see that both plots look very similar: wherever past observations are highly informative about the the present state (the red region in the left plot), we should prefer À 2 } This leads to the memory trace effectively computing an average of recent observations, which is exactly the "accumulating" behavior that is needed when g large and p is small.
In the T-maze example, most histories are not relevant, so their value estimates do not contribute the return error. This makes possible for a large reduce the necessary Lipschitz constant. Another scenario where large À can be effective is highly stochastic environment. Consider the following simple HMM with state space X = {0, 1) and one-hot observation space y = {o, 1). The transition and emission probabilities are given in the diagram below.
6. Experiments
We now evaluate the effectiveness of memory traces as practical alternative to windows in online reinforcement learning. Our first experiment considers the setting of online policy evaluation by temporal difference learning with lin- function approximation. In our second experiment, test the potential of memory traces for deep reinforcement learning.
1 1-
C
I-P
1-9
4
0
1
Temporal difference (TD) learning. The environment that forms the basis for our first experiment is a modified version of Sutton's 's random walk (Sutton & Barto, 2018, Example 9.1). There are 1001 states arranged in a line with state at the left and state 1000 the right. The agent
The probability of transitioning is p. and the probability of an 'error' in the emission (i.e., yt * xx) is These param- eters influence how much each observation can trusted. For example, if g is large, then relying only on the most

---

Partially Observable Reinforcement Learning with Memory Traces
10
20
TD(0) memory trace
TD fixed point (memeeyyess))
window
0.12
0.9
Average return crror
TD(O) concateration
Average total reward
Best memoryless solution
0.8
0.06
0.5
Optinum memory trice
Memory trace (0, Ag)
Window (k)
Optimum full window
bc
0.4
Memay (Ag)
Memoryless
0.2
0.4
0.6
0.7
0.8
0.9
0.95
2
2²
2
2.9
T-Maze corridor length
Figure 4. Return errors achieved with memory traces and windows Sutton's 's noisy random walk environment. The experiments were repeated with 100 different random seeds and the plot contains (invisible) 95% confidence intervals for the average return error.
Figure 5. Average success rate of PPO in the T-maze. If long memory is required, frame stacking not a viable solution, and outperformed by memory traces. The experiments were repeated with 50 random seeds and we show 95% confidence intervals."
starts in the center (state x 500), and in each step is randomly transported to one of the 100 states to its left or right. Should the agent be close to the edge (i.e., x < 100 or x > 900), then the excess probability mass is moved to state 500, so that going over the edge transports the agent back to the center. Additionally, going over the edge on the right gives reward of +1, while going the edge on the left gives a reward of -1. All other transitions give a reward of 0. This environment is partially observable; even though there are 1001 states, there are only | = 11 different observations.
(Chevalier-Boissee et al., 2024) version of this environment, shown inset in Fig. (with corridor length k = 8). and eval- uate the performance PPO (Schulman et al., 2017). The agent starts in a colored tile on left, and, at the end of the corridor, has decide whether to go up or down. If the color of the terminal tile matches the starting tile, a reward of +1 is given. All other transitions result in reward of O.
In Fig. 5, we compare the average success rate per learning episode of PPO when using either memory. In this con- text, the window memory approach is also called frame stacking. To make the maze solvable, we use a window length that is equal the corridor length k. For the memory trace approach, we used two parallel traces with different values of À as input. The first is X 0, corresponding to the current observation, and the second is X = A * as derived in the proof of Theorem 5.8. Also shown are the performances of PPO when using either of these values individually (in this case, À = 0 is memoryless policy). We can see that the memory trace can function as a good alternative frame stacking in tasks where long memory is required. While frame stacking avoids the combinatorial explosion experienced in the tabular case, the neural net- works still become excessively large for very long windows, and learning hecomes difficult. Additional details regarding implementation and hyperparameters for both PPO and TD learning can be found in Appendix C.
the agent is in state x, then corresponding "bracket" 1ooT With probability 0.5, the agent observes this bracket, otherwise the agent receives random observation between 0 and 10.
In Fig. 4, we plot the return errors achieved by TD learn- ing when using either memory traces with linear function approximation or a length-m window ("full window"). For comparison, we also show the best possible return error achievable with either type of memory. can be seen that the trace approach significantly outperforms the window. While the window perform well in theory, in practice, the combinatorial complexity due to the number of possi- ble length-m windows quickly becomes prohibitive. The learned weight vector has [9] parameters in the memory trace approach, but r parameters the window ap- proach. We also show the performance of an alternative window memory which the most recent observations concatenated into single vector, that the weight vector has m Y parameters, Despite this increased flexibil- ity. we see that it does not improve performance over the exponential weighting of memory traces.
R-1
7. Discussion & conclusion
We introduced the memory trace, new type of memory for reinforcement learning. Our analysis compares this
An average success rate of less than 0.5 is result of premature termination with reward of if the maximum episode length of 5(k + 2) steps is exceeded (where the corridor length).
Proximal policy optimization (PPO). We now test the capabilities of memory traces for control. The T-maze has al- ready been introduced (see Fig. 1). We construct Minigrid
8

---

Partially Observable Reinforcement Learning with Memory Traces
feature to the common window memory, where we find that the two concepts are closely linked and even equivalent in some cases. However, we also demonstrate that there are environments that can be efficiently solved with memory traces but not with windows, by characterizing the complexity of learning Lipschitz functions, In contrast to this, we show that the converse statement is not true; there is no environment that can be efficiently solved with windows, but not with memory traces. Our foeus Lipschitz functions is motivated by the geometry of the space of memory traces, and is also of practical relevance, as neural networks have been shown to learn functions with lower Lipschitz constants more easily (Rahaman et al., 2019). We further demonstrate in experiments that memory traces provide an effective alternative windows.
Konidaris, G. Mitigating partial observability in sequen- tial decision processes via the lambda discrepancy. In Advances in Neural Information Processing Systems, vol- ume 37, pp.
2024. LINK. 1,2
Aluffi, P. Algebra: Notes from the Underground. Cambridge University Press, 2021. 3
Bakker, B. Reinforcement learning with long short-term
memory. In Advances in Neural Information Processing Systems, volume 14, 2001. LINK.
Bousquet, O., Boucheron, S., and Lugosi, G. Introduction to statistical learning theory. In Advanced Lectures on Machine Learning, pp. 169-207. Springer, 2003. LINK.
13
Theoretical efforts in the community have mainly focused on analyzing window memory, despite its poor scaling prop- erties. Unfortunately, the resulting guarantees are based on observability assumptions that are often violated (e.g., by overcomplete environments such as Sutton's 's noisy random walk). Memory traces, in contrast, provide a practical fea- ture that is mathematically tractable, and our analysis is first step towards understanding such memory features. An important extension that we leave to future work is char- acterization of the solvability of environments with memory traces and Lipschitz continuous functions in terms of ex- plicit properties of the transition and emission probabilities.
Cayci, S., He, N., and Srikant, R. Finite-time analysis of natural actor-critic for POMDPs. SIAM Journal on Mathematics of Data Science, 6(4):869-896, 2024. LINK.
2
Chevalier-Boisvert, M., Dai, B., Towers, M., Vicent,e R., Willems, L., Lahlou, S., Pal, S., Castro, P. S., and Terry, J. Minigrid & Miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks. Advances in Neural Information Processing Sys- lems, 36:73383-73394, 2024. LINK. 8
Efroni, Y., Jin, C., Krishnamurthy, A., and Miryoosefi, S. Provable reinforcement learning with short-term mem- ory. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Ma- chine Learning Research, pp. 5832-5850, 2022. LINK.
Acknowledgments
We thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for their support. M. Muchlebach is funded by the German Research Foundation (DFG) under the project 456587626 of the Emmy Noether Programme. C. Vernade is funded by the German Research Foundation (DFG) under both the project 468806714 14 of the Emmy Noether Programme and under Germany's 's Ex- cellence Strategy EXC number 2064/1 Project number 390727645.
1,2
Esslinger, K., Platt, R., and Amato, C. Deep transformer Q- networks for partially observable reinforcement learning. WiXiv:2206.01072 2022. LINK. 2
Federer, H. Geometric Measure Theory. Springer, 2014. 5
Golowich, N., Moitra, A., and Rohatgi, D. Planning and learning in partially observable systems via filter stability. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 349-362, 2023. LINK. 1, 2
Impact statement
This paper presents work whose goal to advance the field of machine learning- There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Graves, A., Wayne, G., and Danihelka, I. Neural Turing machines. arXiv: 1410.5401 2014. LINK. 2
Hausknecht, M. J. and Stone, P. Deep recurrent Q-learning for partially observable MDPs. In AAAI 2015 Fall Sym- posium Series, number pp. 29-37, 2015. LINK. 2
References
Allard, T. and Böleskei, H. Ellipsoid methods for metric entropy computation. arXiv:2405. 1066, 2024. LINK. 4
Haussler, D. Decision theoretic generalizations of the PAC model for neural net and other learning applications. In- formation and Computation, 100(1):78-115) 1992. LINK.
Allen, C., Kirtland, A., Tao, R. Y., Lobel, S., Scott, D., Petrocelli, N., Gottesman, O., Parr, R., Littman, M., and
9

---

Partially Observable Reinforcement Learning with Memory Traces
Huang, S., Dossa, R. F. J., Raffin, A., Kanervisto, A., and Wang, W. The 37 implementation details of proximal policy optimization. In ICLR Blog Track, 2022. LINK. 16
Tao, T. An Epsilon of Room, I: Real Analysis. American Mathematical Society, 2010. 13
Tao, T. Metrie entropy analogues of sum set theory. What's
new, 2014. LINK. 14
Liu, Q., Chung, A., Szepesvari, C., and Jin, C. When is partially observable reinforcement learning not scary? In Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 5175-5220, 2022. LINK.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M.,
Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al. Grandmaster level in starcraft using multi- reinforcement learning. Nature, 575 (7782)3350-544 2019. LINK.
Loch, and Singh, S. P. Using eligibility traces to find the best memoryless policy in partially observable markov decision processes. In Proceedings of the Fifieenth Inter- national Conference on Machine Learning, pp. 323-333,1 1998. LINK. 2
Wainwright, M. High-Diimnsional Statistics: A Non- Asymptotic Viewpoint. Cambridge University Press, 2019. 4
A. Further results on injectivity
McCallum, R. A. Overcoming incomplete perception with utile distinction memory. In Proceedings of the Tenth International Conference on Machine Learning, pp. 190- 196, 1993. LINK. 2
The injectivity result of Theorem 4.1 holds only if ratio- nal and histories are finite. We now justify these constraints with two counterexamples.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Ve-
Example A.1 (Irrational A). Consider the observation space
ness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wier- stra, D., Legg, S., and Hassabis, D. Human-level control through deep reinforcement learning. Nature, 518(7540); 529-533. 2015. LINK. 1
consisting of y! (L, 0) and y² (0, 1). The history
h = (y' y² v²) leads to the memory trace
2x(h) = y 2v X²y² = (1,*+
If Φ - 1, where - = is the golden ratio, then 2 (h') (1. By symmetry, the same memory trace will thus be obtained for the history N' = (v² ,,',y))
Ni, T., Eysenbach, B., and Salakhutdinov, R. Recur- rent model-free RL can be a strong baseline for many POMDPs. In Proceedings of the 39th International Con- ference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 16691-16723, 2022. LINK. 1
Example A.2 (Infinite history). Consider the same observa- tion space as in Example A.1. Let (y² y² y2 ......) and W (y² y ,...,,...) be two infinite histories. Then, with A 2
Dc
Nikulin, A., Kurenkov, V., Zisman, I., Agarkov, A. S., Sinii, V., and Kolesnikov, S. XLand-minigrid: Scalable meta- reinforcement learning environments in JAX. In The eight Conference on Neural Information Process- ing Systems Datasets and Benchmarks Track, 2024. LINK. 16
2x
1,
2
= (1,
k=
Thus, the traces are equal by symmetry.
Note that the above examples only work because À 2 2. For A < 1. injectivity is guaranteed by Lemma 4.3, We now extend this result to linearly dependent observation spaces.
Rahaman, N., Baratin, A., Arpit, D., Draxler, F., Lin, M., Hamprecht, F., Bengio, Y., and Courville, A. On the spectral bias of neural networks. In Proceedings of the 36th International Conference on Machine Learning, vol- ume 97 of Proceedings of Machine Learning Research, pp. 5301-53100 2019. LINK. 9
Theorem A.3. For all finite sets y c Q", there exists a set A C Q that is dense in (0, 1) with the property that if X E A, then 2 is injective for finite histories.
Proof. We follow a similar argument as in the proof of Thcorem 4.1. Let h and h be two distinct finite histories that are O-padded. We write 2 = 2 (h) and z' = 2hh).. Let e1, ....... ED denote the standard basis of R. As yo C Q". each y² Yo can be written
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv: 1707.06347, 2017. LINK. 2,8
D
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. MIT press, second edition, 2018. 2,
Psj
Cj.
Ois
j=1
10

---

Partially Observable Reinforcement Learning with Memory Traces
m
0
m
m = 2
m = 3
m 4
m 5
m71
m = 7
0.3
X 0.5
A 0.7
0.8
0.6
0.4
0.2
0.0
-0.2
-0.5
0.0
0.0
0.0
0.6
0.2
-0.2
0.2
0.5
21
0.6
0.2
-0.2
0.5
21
0.6
0.2
-0.2
0.5
21
22
22
Figure 6. visualization of trace space, where y one-hot with [3] 4.
To visualize the four-dimensional space, we perform an
orthogonal projection onto the thrce-dimensional space described by (4).
with Pij and qi coprime integers.
A
L E Q Vi, E
[[Voll.] E [D]:
Nol
yal
x'_
cc())
Pij
Pij +
Pijj q/'
Pij qi
Pirj
190
1
4sp
4kt
qe'
k=1i=1
(A
where and q are coprime, and m n means that does not divide n. We first show that A is dense in R. Let a < b be two real numbers. As the rational numbers are dense in R. there must exist a number & E Q with ý and q coprime and q > 1, such that 0 new rational number in (p, b) C (a, b) instead.) Let n > 1 be natural number such that
where a; is defined in (3). By linear independence of the standard basis, we see that & = 2' only if By (A) = for all j E (D). By (3), we can expand (3 as
00
Mol
(If q = 1, we can create
B₂(A) =
Pij
(
1²1 1V' v'))-
k=0
Let is and 142 be the indices (with respect to yo) of the observations k steps ago, for h and h', respectively, such that V-a 1it and v = y We can then write 3, as
max
c b b 6-p/a/
where
B5(A) = Σ x
Piaj
PiLi
1Mol D
Pia.
90,55
-= max
Pij
9kl
a elVll
qr
As the histories h and h are distinct, there must be a ko such that the corresponding observations are distinct, y- * y' No The coefficient of the A term in By must be nonzero for at least one j E [D], as we would otherwise have
jE(D
k=1l=1
We now define
=pqm pppn11 + and = q". Then,
p
p 1 E (a.b).
V- V/K
Σ
Pinod
Pla )ez O. 4/
If p and are coprime, then P E A, as g is too large to divide any of the integers that the definition of A prohibits it to divide. Let be prime factor of q = q" Then, is prime factor of q and hence also of p - p But then, cannot be a prime factor of p. Thus, p and y are coprime, and so P E An (a, b). As and b were arbitrary real numbers, we have shown that A is dense in IR
King
which is a contradiction. Thus, we have shown that there exists jo E [D] such that 3 has at least one nonzero co- efficient. In the following we introduce the set A, which we show to be dense in the real numbers, and finally we com- plete the proof by showing that E A implies 3 (A) o
The set A C Q is defined as
Finally, we show that no À E A is root of By0- Assume, for the sake of contradiction, that there exists a 4
2 E A,

---

Partially Observable Reinforcement Learning with Memory Traces
with p and q coprime, such that (A) 0:
Vi, E []Hol, E [D]]
{PU F Prij = q t (pis - -p2))}
00
Piada
Picio
Vd (-1,
Jiu
96,,50
gtl.
1yal D
Pieda
Piç,io
9is
O.
Thus A = Q Z.
K= di
96,,00
d= 1=
B. Proofs
CxEZ
Then, by the rational root theorem, q divides the highest- order coefficient Çj. which we now know is nonzero. However, the definition of A prohibits g from dividing integer of this form. Thus, we know that no X E A is root of $3o (A), and we can conclude that # z'-
In this section we present all proofs that are omitted in the main text.
Lemma 4.2 (Concentration). Let h and h be two histories
of one-hot observations such that winm (h) = win. (h) for some m. Then, the corresponding traces satisfy
How is the set A to be interpreted, and why does A = Q Z does not always work? Consider the observation space
(1) zx =x(b)] V2
y = {0, 23 C Q. which is not linearly independent. If
Proof. Without loss of generality we can assume the histo- ries are infinite (by applying O-padding). By expanding the distance, we get
= 2. then the histories h = (1, and It' = (0, 2) will both produce the memory trace z = 1. To build the set A, we first rewrite each observation as y
ps As all
||a((h) 2x(1l
observations are integers, Q: 1 for all three yy E y. Thus, looking at the definition of A, we have for a & E Q, with p and q coprime, that 2 E A if and only if,
= -11-))112
(v- x-*)]
q
Hul
Vi E [18oll
{ +
pt qi
Pv
+
q
Pi
Pe
II k=1
9k
S (1 - A)
11yy-mmm - 8-k-mll
qu'
qi
4:'
Vi, E [ : {pr + Pe = q & (p. - p
S 22
e +2] : td
Lemma 4.3 (Separation). Let h and h be two histories of one-hot observations such that win, (h) * winm (h) for some m. Then, if X S 1. the corresponding traces satisfy
22
We thus see that A- Q 1z. Thus, for 0 < X < 1, our choice of A = was the only point where A differs from
(1x(1) xx(1l vτ(1 - 22X)A"1
Q X Z.
Proof. We write 2X" - 22 win.. Without loss of gener- ality we can assume the histories are infinite (by applying O-padding). By making use of the reverse triangle inequality, we get
relevant special case of this result is concerned with 0-1- encodings of the observations. The next result shows that, in this case, the set A is identical to the one in Theorem 4.1.
Corollary A.A. y C 10 and X E Q Z, then zx is injective for finite histories.
(1)) 22 2x)l
Proof. We will show that the set that is constructed in the proof of Theorem A.3 is exactly A Q x Z for this choice
= =(1-
- -y-=1
of y. All y² Yo can be written as
k=0
11xx((() 2xf(hh
Pele Ej.
y¹
+ (1 A) Σ
1 - 9-1)]
kmm
with gi and Pr.j E (0, for all i [[Vol] and j E D. Thus, if x= 2 E Q. with p and g coprime, then À E A if and only if,
> [1 (h) - 2x (h)l
(1 X) 1 --10)
Vi, E [[Ho]],j E [D]:
1901 D
We will show that the first term is bounded below by
Pij # Pi'j r
Pij
Peo
[1x - 2x)) 2 v2(1 1)
96
q/3
qi j
2mm1
12

---

Partially Observable Reinforcement Learning with Memory Traces
whereas the second term can be upper-bounded using the triangle inequality and the fact that Ily-k U-*ll I 22:
|| (h) 2x =xx+1 '(b]l
2 (1 - >)ller - -l -11=3 - (1-1))
2 22 - A) -2((1 )
(1 (1-A) Σ
2 /2(1 - A) - -V2(1 - -1
k=
S S S 12 1)AM-1
= /2(1 A)A"
where we used À S 1 in the last step. This allows us to drop the absolute value in our bound above and get
where we have again used that À S 1 2
Lemma 4.4. If' is one-hot, then the Minkowski dimension of Zx is, for all X < 1
(1x) - (xxIl| 2 v2(1 \)A V2XT
= 22 21)
dim(Zx)= = log |3] = dx- log(1/A)
as desired.
To prove the lower bound on the first term, we perform induction m. For the base case
For all X E [0,1), 1), we have dim(2x) S min - 1, dx
(a single obser- vation), win.. (h) a winm (h) implies that y * y. We thus have [}= - ( = 22 \). satisfying the desired inequality.
Proof. The set ZA a self-simitar fractal, which means that it is composed of several scaled and translated copies of itself. In particular,
We now suppose that the result holds for some m E N. and consider the case of two histories h and h such that wilm+1 (h) j winm+1 (h). Using the reverse triangle in- equality, we have
2, = A2, + (1 - A)y.
where the scalar multiplication is applied to every element of the set, and the addition is the Minkowski addition which adds all pairs of points of the two sets. Thus, 2, consists of precisely | copies of itself, each scaled by X. If < 2. then Lemma 4.3 guarantees that these |У] smaller copies do not overlap (this is also visualized in Fig. 2). The results now all follow directly from known properties of the Minkowski dimension (Tao, 2010, Section 1.15.1). The upper bound of
|| 12 (n) - 2x m++ (h)]l
(11- A) Σ -()-)-ū-x))
= [1(1 (y - 7) + +1 - (h-1))
2 (1 1)lly Øl1 - >11=3((h11) - 2x" (h1)) (6)
| 1 follows from (4).
There are two cases to consider. First, suppose that y = y. such that the first term in (6) is (1 Ailly ツl = 0. In this case, we know that winm (l--)) + winm 1).. since otherwise winm+1(h) (f) = winm+1(h). Thus, the induction hypothesis and (6) guarantee that
Theorem 5.1 (Hoeffding bound). Given dataset of n tra-
jectories from an environment ε, a function class T, and some 6 > O, let F be the smallest e-cover of F and fn. = arg min Re (f). Then, with probability at least 1 8.
||xxt11 (h) 2x m+1 (h)] 2 X1|2X
+
2x (h-1)
A2 Hz) + log
2²
2 2(1 AA
Re((n) < Re (F) + (F)
+ cA
2n
2'
Now, suppose that y # y. such that |/l - 1l| = 22. We can upper-bound the second term in (6) by making use of the triangle inequality and the fact that x S (1 A):
where we have desined A - 1-2 n.
Proof. In the language of statistical learning, the return error R = Rg a measure of risk, and the empirical return error R., is the corresponding empirical risk. The argument presented here is standard (cf. Bousquet et al., 2003, Section 3.5). Let Se = arg min sEz. R(J)) We have,
(h-1) - xx² II1I
x11 x>|l Σ (
k=
S 2 - - > v v2 x) X).
R(fa) - R(F = R(f,.) RRn + (n,) - R(fa)
Thus, the first term of (6) dominates the second term, and we can drop the absolute value:
< R(fn) - (fa) + Rnc) R(())
S 2 max (R(() - (f)..
(7)
EEt.
13

---

Partially Observable Reinforcement Learning with Memory Traces
Hoeffding's 's inequality states that if (&:)=1 are indepen- dent random variables with mean ja that are contained almost surely in the interval [a, bj. then
Lemma 5.3. Let m E No be a window length. Then, the metric entropy of F' for all > 0,
(F = 1 log 2E
( ( (b-aa3 a)3
2n12
E u 2
2n
f 2exp
Thus, as a function of m. (3m) E ((
for any 17 > O. We can apply this inequality to our setting by
Proof. An e-packing of a set I is finite subset 9 C J with the property that, for any f.g E S it holds that f 2 e. The e-packing number (3) of J is the cardinality of the largest c-packing of g. This number is closely related to the covering number (F) defined earlier. Let > 0 and let Ie and g be an E-cover and 2e-packing of the set F. respectively. Then, it holds that (Tao, 2014)
defining (t) = 1 [vo: v-1....) Ei= 3'r((++)) } for f E E.. Then, fa(f) E [0, 22 almost surely for any f. These variables are independent since the dataset is i..d.,
so Hoeffding's ss inequality applies. In particular, we see that
(f) = 1 Σ ff and 3( = E [[(n =(f).
|s S (2) S (.) 19%1-
(8)
Thus, for 17 > 0, we have
We will prove the result by finding set F for each m E No and each e >> 0, that is simultancously an e-cover and a 26- 26-packing of Fm- By the inequality above, this implies that (Fm) = log [5 The set we consider is
P(2 max (R(()) - Rxx SEt+
P U (IR(F) R() 2 n/2)
EE3
F = (f winm I y + V.. C F
$ Σ (((R(() Rn(1)1 2 n/22
where V. is a set of [2/(2c]] points in [u, o] that both e-covers this interval and 2e-packs it. The set V. exists because can fit [A/(2e) uniformly spaced points with equal distance 2c into the interval, since this only requires a length of [2+(2)) )- 1 (2e) < A. Taking these points as the centers of c-balls, we see that the total volume covered by these balls is | (2e( (2e) (2e) Z A, since there is no overlap. Thus, if placed at an appropriate position in [u. ø). these points both cover an pack the interval desired.
/E9
2mm
$ 2 exp
= 5.
A
Solving for n, we get that with probability at least 1 - 5,
2 max R()) - (f) S 5n= A2 log [ + log 3 FES
2n
The final result follows from (7), Lemma 5.2 (where we let
Now consider the set F Let f.g E Fr be two distinct functions. Then, there must be some history h such that f(h) # g(h). As f(h), g(h) E V., this implies that [ g(h)l 2 2e. In other words, - 2 2c, and so 9x is a 2e-packing of Fm. Now let f FF.. Then, for every history h. there exists a value (since V. covers le, t)). Define g E 3h such that (h) is exactly this ö V. for each history h. Then, |lf - ollo0 c, and so Fhe is an 6-cover of I Thus, we have
9 = Ir,, and the definition of metric entropy.
Lemma 5.2. Let & be an environment, F a function class, and O. If9 is an e-cover of F, then
V. such that 1 f(h) < e
Rg) S (F) A + 2
Proof. Define f E as f = arg mii Re (J') and let g E 9 be such that ||s gloo0 S Then,
H. (Tm) = log Isee = log [V |V.] M logl logl A
(9) S 2R
Ro
Ee (athho) Σ t=0
>'r(()++)) )}
Lemma 5.7. Let |9] > 1. If < 1.2 then dx < 19 - 1.
-Ee (Eelfg(ho) - -(hoo) + f(boo) - -Ro}?
Proof. As | 2 2. we have
S <Ee [Eelfc+If()) - 2
M
= -Eele + 2e (hho)
) - Rol + 1s(hh) - Rol
<
19 +1
s 2Re (F) + 2.A + 2
(19)
+ 1)-1
M
+
1
14

---

Partially Observable Reinforcement Learning with Memory Traces
1 1X
|9] >
(l + 1)
Table 2. T-maze value function for 'always-up' poliey
B ा
[| + 1) 1
History h v(h)
Thus, | is increasing in 18). and therefore, |8] 2 2. the minimum is achieved when | = 2, which yields
ao
bo
0
ao k
xx
+1
2 = From this, it follows that
bo k
x
-1
ao k
y
A
bot Py
+1
other
| --
log |
log(1 /A) > /
Before observing D/-1, the value must be 0 since both and are equally likely, and u4-1 will thus result in a reward of +1 or -1 with equal probability. All histories other than the ones in the table above can have an arbitrary value (denoted ehh) = above), since the probability of these histories is O. To represent this value function accurately with length-m window (where consider the 0-padded histories), it is necessary that m 2 k, since it would otherwise be impossible to differentiate between k x and bo* This already gives us the first result. Using Lemma 5.3 (with A 2), m 2 & implies that, for all 0,
log |8]
|
(12(
dx
| 1.
Theorem 5.8 (T-maze). There exists sequence (Ex) of enviromments (with constant observation space Y) with the property that, for every e >> 0 and every k E N.
min mm) |
= 0} E *) and min (xx,.) Re, (Fx...) = 0} 11
AL
H. (Fm) 2 | log[1// [1/]] ((y))t)
Proof. The T-maze environment &N with corridor length
k is defined as follows (see Fig. 1). There are |3] 5 possible observations, y = (a. b, o, x, y), each encoded as a one-hot vector in RR An episode starts at the left of the corridor, where the agent receives either observation y/ = a or yo = b, each with equal probability. Moving along the corridor to the right, the agent receives the observation o every step until, time of the corridor, where the observation yk-1 is, with equal probability, either x or y. At this point, the agent has to decide whether to go up (+) or down (J), after which the episode ends. The reward it receives in the final step is determined by the following table.
We now construct function in Fx,t, where À = = and L = /2ek that achieves a return error of 0. This implies, by Lemma 5.4, that for all e > O,
2
2v 2ek M 1
191-
(. S log
E O(
k- 1, it reaches the end
We define f= f a by setting f(x((h) = v/h) for each (0-padded) history h in Table 2 and extending f to Lip(f)- Lipschitz continuous function f: [o, 1] 1-1, using Kirszbraun's 's theorem. This ensures that f accurately repre- sents the value function. To complete the proof, we need to verify that Lip(f) < L. We thus check all pairs of histories in Table 2 whose values are not equal. Checking the first pair yields
Table I. Rewards in the T-maze
yo
a
V/o
Up 1 = +
+1
( 1 - 2xo
1
U4 = +
-1
+1
Uk = +
-1
+1
=vē(1 - 1)(=-1=
V2
V2
yk-1
0k 1 +
+1
-1
k(1 + k-1
R-1
ek
This is equal to ||=x - =x -y))l by symmetry. Checking the next pair yields
All other transitions give reward of 0. We consider the fixed policy that always goes up (1) at the end of the corridor. Our goal is to estimate the value function of this policy. The true value function is given by the following table (where histories are written left-to-right and E (0....,k .k 2)).
||ox k- -2x) - >x =20 -2)))
= - --])]|[x - yll -2(11 A) v2/k.
15

---

Partially Observable Reinforcement Learning with Memory Traces
which is equal to || (xx (00)===x0ooo--000 2 by symmetry. Checking the next pair yields
keep the step size constant at a 0.02 for all values of for the memory trace. This is the reason why it looks like memory traces are slightly worse with À = 0 than windows with m 1; this discrepancy would disappear if we also optimized the step sizes in the memory trace experiments.
2x) -xo'_l
= =1(1 - 2)x + (ax(ao"-2) (ao'))
2 - 2) = 1/h.
1(1-A)x
Table 3. PPO hyperparameters
where we have used the Pythagorean theorem. This is equal Iao 2y) 2A =x(a0")) (bo " 2x)
Parameter
Value
21 (bo')]l. and (bo -2) zx [b by symmetry. Similarly,
Total number of steps
1, 024, 000, 000
Number of parallel environments Number of steps per update
16
128 16
1|ax -x)
2x) - 2사 (bo'))l
Learning rate
0.0003 - 0
= =1 - A)х + λex - 22 (bo'))
Generalized ad advantage estimation À
0.95
Number of epochs
2
2 - 2) 1/h:
-11-11x
Number of minibatches
8
Clipping parameter
0.2
This is equal to ||=
=1 =x(b))]l, || 1=x
Value loss weight
0.5
=x (ac*) Il. and (bx 22) =x(ao')) by symmetry. Fi- nally,
Entropy coefficient
0.01
Maximum gradient norm
0.5
1=x(ao==30) -
=1(1 11((x-x1)) M=x(ao * -)- - 2b0 2-
2 22(1 A) V22k 1(1-)1(x-3)
by symmetry. The Lipschitz constant of now satisfies Lip(f) < 2/d, where d = v2/(ek) is the smallest of the distances above. Thus, have Lip(f) < L desired.
which is equal to (1=x(a0*~2y)--
C. Implementation details
Our implementations of both TD learning and PPO, well the two environments (Sutton's noisy random walk and the T-maze) are available online at https:: //gttub. o aatboeeberhaarr/mmmmmr...
Our PPO implementation is based on Huang et al. (2022), and the Minigrid T-maze environment implementation uses the xmini n gri d library (Nikulin et al., 2024). The hyper- parameters used in PPO experiments are compiled in Table 3. We performed hyperparameter search over the discount factor y E {0.9, 0.99, 0.999} and plot the results using the best performing values in Fig. 5. Both actor and critic have a neural network architecture of two hidden lay- ers with 64 neurons each and tanh activation functions. We used the Adam optimizer with linear learning rate decay from 0.0003 0 suggested by Huang al. (2022).
Our TD experiments ran for 100, 000 steps and we per- formed hyperparameter search for the step size a over a range of 13 logarithmically spaced values between 0.0001 and 1.0. Fig. 4, we show the results using the best step size for each individual value of the window length m, but
16


Reviews:
[{"review_id": "mEolwRZOi7", "reviewer": "Reviewer_tJLm", "summary": "The authors propose a novel method for handling observations in reinforcement learning for partially observable systems.\nTheir method represents the history of observations with an exponential moving average. The authors analyze sample complexity bounds for offline on policy evaluation. The novel method is compared with the traditionally used moving windows both theoretically and empirically.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you very much for your positive review! Below, we respond to your critical points and questions.\n\n> I think it would have been interesting to discuss the use of RNNs and transformers to represent the history of observations.\n\nWe are happy to include a brief discussion of the connections to RNN and transformer-based methods. Indeed, it is possible to view memory traces as a kind of simplified RNN, while the window-based approach has a fixed context length like transformers. Based on the other reviews, we will include references to https://arxiv.org/abs/1507.06527 and https://arxiv.org/abs/2206.01078.\n\n> The evaluation is on relatively simple tasks. Exploring a broader range of environments could further establish the generality of the approach.\n\nIndeed, the environments we consider in our experiments are more illustrative than realistic. We intend the main contributions of this paper to be theoretical, and we are working on a follow-up project in which we investigate memory traces empirically in more complex environments. The reason for this is that a more thorough empirical evaluation requires a lot more work. For example, the assumption of one-hot observation only makes sense in small tabular POMDPs. A proper treatment of these issues therefore goeses beyond the scope of this paper.\n\n> It would be interesting to discuss how to choose $\\lambda$ in different environments.\n\nWe agree that this is an interesting question that is not fully addressed in the paper. All that our theoretical (and empirical) results suggest is that $\\lambda$ should usually be larger than $\\frac{1}{2}$, as otherwise a window could be used instead. In our follow-up work, we investigate whether it is possible to learn $\\lambda$, and if there is a way to connect properties of the transition and emission dynamics of the POMDP to the optimal choice for $\\lambda$.\n\n> Do you assume the agent remembers its actions? Actions also provide important context for the agent.\n\nIn this paper, we define memory traces only based on the observations. However, it is easy to include actions in the traces as well by regarding them as observations, i.e., by considering the augmented observation space $\\tilde{\\mathcal Y} = \\mathcal Y \\times \\mathcal U$.\n\n> I am more familiar with different descriptions of the POMDP setting, where the reward is a mapping from the latent state to the reward. Does this impact the proposed method?\n\nThese two descriptions of POMDPs are equivalent, so it would not impact the proposed method. Given a POMDP with state space $\\mathcal X$, observation space $\\mathcal Y$, set of possible rewards $\\mathcal R$, emission probabilities $p(y \\mid x)$, and state-reward function $r: \\mathcal X \\to \\mathcal R$, we can consider the equivalent POMDP with observation space $\\tilde{\\mathcal Y} = \\mathcal Y \\times \\mathcal R$, emission probabilities $p(\\tilde y = (y, r) \\mid x) = p(y \\mid x)[r = r(x)]$, and observation-reward function $\\tilde r(\\tilde y = (y, r)) = r$. \nWe use the observation-reward definition because it emphasizes that rewards are also quantities that are observed by the agent. In this model, state and reward are conditionally independent given the observation. With the state-reward definition this is not the case, so rewards would technically need to be included explicitly in memory as they could also give information about the state. We are open to changing our definition if it is confusing.", "claims_and_evidence": "All claims are supported by evidence.", "methods_and_evaluation_criteria": "The authors use classical benchmark tasks that are well suited for the problem at hand.", "theoretical_claims": "I did not independently verify all the proofs in detail.", "experimental_designs_or_analyses": "The experiment contains classical benchmark tasks and compares to the traditional method of moving windows.\nThe experiments for value evaluation and for control are sound.", "relation_to_broader_scientific_literature": "This paper is a theoretical contribution to the POMDP literature. While most current methods use neural network based approaches like RNNs or transformers, they lack theory. This paper contributes to the understanding of observation history representation in POMDPs.", "essential_references_not_discussed": "I think it would have been interesting to discuss the use of RNNs and transformers to represent the history of observations.", "other_strengths_and_weaknesses": "Strength:\nThe authors effectively introduce the concept of memory traces with a well-designed example in Figure 1. This simple yet insightful illustration (using the T-maze environment) clearly demonstrates the motivation behind memory traces and their advantage over traditional window-based approaches.\n\nWeakness:\nThe evaluation is on relatively simple tasks. Exploring a broader range of environments could further establish the generality of the approach.", "other_comments_or_suggestions": "It would be interesting to discuss how to chose $\\lambda$ in different environments.", "questions_for_authors": "Do you assume the agent remembers its actions?  Actions also provide important context for the agent.\n\nI am more familiar with different descriptions of the POMDP setting, where the reward is a mapping from the latent state to the reward. Does this impact the proposed method?", "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": "", "extra_scores": {}}, {"review_id": "ZwLIWdbaMT", "reviewer": "Reviewer_s69o", "summary": "The authors propose memory traces as an alternative to fixed-window histories, or “frame stacking,” for addressing partial observability in RL. The concept is loosely related to eligibility traces, amounting to an exponential moving average of the observation stream, which is then fed to the agent as input for the value function and/or policy. The authors prove conditions on $\\lambda$ for injective-ness (when the trace is a sufficient statistic for the history), separability, and concentration. Analysis for offline on-policy sample complexity (in terms of minimum value error) is also given, including theorems that relate memory traces to fixed-length windows, and vice versa. The T-Maze environment is given as an instance where memory traces can be proved to be more efficient than windows. Finally, traces and windows are compared in a partially observable random walk, and again in the T-Maze environment using PPO (a deep RL agent). In these environments, memory traces are shown to achieve lower value error and higher average reward, respectively.\n\n**Score raised from 2 to 3 after rebuttal**", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you very much for your thorough review of our paper! Below, we respond to your critical points and questions. Due to limited space, we cannot respond to every point, but we will do our best to incorporate all your suggestions in the final version.\n\n**Proof of Theorem 5.8 and the choice of $\\lambda = \\frac{k - 1}{k}$ in the T-maze.**\nThe full proof of Theorem 5.8 is in Appendix B (p. 14). In this proof, as well as in our PPO experiment, we fix the forgetting factor to $\\lambda = \\frac{k - 1}{k}$, where $k$ is the corridor length of the T-maze. Importantly, this corridor length is fixed, and does not change during an episode; it is not to be confused with the time step $t$. Thus, $\\lambda$ is **not** dynamic, and the memory trace is indeed an exponentially weighted average.\n\n**Concerns about the PPO (T-maze) experiment**\n- In the PPO experiment, we additionally give the memory trace agent access to the current observation (or, equivalently, we use a second memory trace with $\\lambda = 0$). We did not do this to give an edge over the frame stacking agent. Indeed, the frame stacking agent also has access to the current observation. Instead, it was a heuristic choice and a demonstration that a practitioner is not constrained to using just one memory trace. We are happy to run additional experiments with only a single memory trace.\n- We use the Adam optimizer with a linear learning rate decay from $0.0003$ to $0$ as suggested by [Huang et al. 2022].\n- In the T-maze minigrid, the agent receives a reward of $1$ if it succeeds, and a reward of $0$ if it does not (and $0$ in all nonterminal transitions). Thus, the \"average success rate\" is the same as the \"average total reward\". A random agent would achieve an average success rate of $0.5$. The observed performance slightly below $0.5$ is due to episodes exceeding the maximum episode length of $5(k + 2)^2$ steps in a T-maze with corridor length $k$. We will clarify this in the article. Does this address your concerns about the Y-axis in Figure 5?\n\n**Concerns about the TD (random walk) experiment**\n- Thank you for your feedback. In this experiment, our goal was to compare memory traces to the full window approach whose sample efficiency we analyze in Sec. 5. However, we agree that we could instead concatenate observations to improve sample efficiency, as we do in the PPO experiments. While we are not aware of this approach in the context of linear function approximation, we ran the experiments that you suggested, please see [here](https://anonymous.4open.science/api/repo/icml2025-rebuttal-trace/file/sutton-concat.pdf). All three algorithms ran for 100,000 steps (1/100th of Fig. 4) with a grid search over step sizes. We see that concatenation makes it possible to learn with very long windows, and that this approach almost reaches the best value error of memory traces. However, it requires almost 20 times the memory to achieve this, and it lacks the theoretical guarantees that we develop in Sec. 5.\n- The step size used in the original TD experiments (Fig. 4) for the window approach is $\\alpha = 0.0001, 0.0002, 0.005, 0.05, 0.2, 0.5$ for $m = 1, 2, 3, 4, 5, 6$, respectively. These values were chosen by a grid search optimizing the average value error. For the memory trace, the step size was kept constant at $\\alpha = 0.0002$ for all values of $\\lambda$. This value was also determined by a grid search.\n\n**Further points**\n- We will expand Appendix C in the final paper. (optimizer, step sizes, ..)\n- Essential References. Thank you for these suggestions. We will include them in the final version.\n- Relation to eligibility traces. We do believe that there is a close connection to eligibility traces, and will include an extended discussion in the final version.\n- Definition of sample efficiency. A low minimum value error does not correspond to low sample efficiency. Could you please explain what gave this impression? We use Theorem 5.1 to tie sample efficiency to the metric entropy.\n- Definition of environment $\\mathcal E$. In our definition of $\\mathcal E$, the policy is assumed fixed (line 107).\n- More realistic experiments & observation-reward function. Please see our response to Reviewer tJLm.\n- Q1: Lack of injectivity guarantee. Could you please elaborate on this question? We provide one experiment in a continuing environment and one in an episodic environment.\n- Q2: \"Traces cannot outperform windows\". In a fully observable POMDP, we can use $\\lambda = 0$ to achieve the same result. Theorem 5.5 guarantees that, if learning with windows is tractable, then learning with traces is also tractable.\n\nPlease let us know if you still have any concerns, or if our responses were not satisfactory. If you agree that we have addressed your questions and provided the necessary clarifications, we kindly request raising our paper’s score based on the responses provided. We are happy to incorporate further feedback into the paper to improve clarity and remove ambiguity.", "claims_and_evidence": "Claims are generally supported with convincing evidence.", "methods_and_evaluation_criteria": "Overall, the methods and evaluation criteria are pretty good, aside from some experiment design concerns I have in **Experimental Designs or Analyses**.\n\nI think it would be beneficial to test in environments that have more partial observability, as T-maze requires remembering essentially 1 bit of information over just a few time steps.\n\nI also feel that some important baselines are missing, such as RNNs or attention. It is already well-known that a fixed-window strategy is the most naive approach for addressing POMDPs and that it does not scale well. Thus, strictly outperforming a window when there are more sophisticated techniques widely used does not feel sufficient to me.", "theoretical_claims": "The theoretical claims are correct, to my knowledge.\n\n~However, the proof of Theorem 5.8 is surprising, as it prescribes setting $\\lambda = (k-1)/k$ in the T-maze. In this case, the exponential average degenerates into an unweighted average of the past $k$ observations, sacrificing the injective guarantees of Theorem 4.1. Does this suggest that truly exponential traces are actually suboptimal in this environment? It seems to contradict the main message of the paper.~", "experimental_designs_or_analyses": "- Random walk\n  - The comparison is unfair here. If I am understanding correctly, the authors’ method uses linear function approximation to evaluate the memory trace, but the fixed-window baseline uses the (integer) history to index into a table. Clearly, the approximation method will perform better due to generalization. It would be far better to produce a window history by concatenating $m$ one-hot vectors; that way, both methods can use linear function approximation. Without this, I am skeptical of the results.\n  - The step-size selection is not explained in sufficient detail. It is not reported what step sizes were used to generate Figure 4. The criteria for “best” step size is never defined.\n- Deep RL\n  - For some reason, two memory traces are given to the authors’ method instead of one. One trace has $\\lambda=(k-1)/k$ and the other has $\\lambda=0$. This seems unfair for two reasons: ~it has a dynamic $\\lambda$ and is not a true exponential average (as I discussed above) and~ it seems to give the agent an extra hint about the current observation. I cannot figure out why this was done other than to make the authors’ performance look better than reality.\n  - The PPO optimizer is not discussed. It would not be possible to reproduce the results in the paper from their description.\n  - Figure 5 says “average success rate” in the caption but the y-axis label says “average total reward.” I am not sure what the real metric is supposed to be.", "relation_to_broader_scientific_literature": "There is a short related work section in which the authors cite three papers which theoretically analyzed windows of fixed length. It does not appear that any previous works studied exponential windows. Some deep RL papers which use windows as input are mentioned. There is no discussion of more sophisticated memory techniques, as far as I see.\n\nA short discussion regarding the inspiration from eligibility traces is also included. However, the relationship to eligibility traces is merely coincidental, in my opinion, and is overemphasized in the paper. TD($\\lambda$) is technically not an exponential average; the weights do not sum to $1$ and nothing is being averaged. The approaches are orthogonal; it would be possible to have an eligibility trace in which the feature vectors are obtained using the memory trace proposed by the authors.", "essential_references_not_discussed": "Deep RL using RNNs or attention, e.g.,\n- DRQN: https://arxiv.org/abs/1507.06527\n- DTQN: https://arxiv.org/abs/2206.01078", "other_strengths_and_weaknesses": "**Strengths**\n- The injective nature of memory traces (histories can usually be uniquely recovered) is surprising and interesting. I like the visualization of the trace space as a Sierpinkski triangle (Figure 2), which helped convince me that this is true.\n- The $\\lambda$/$m$ sweep in Figure 4 is a nice comparison of the two different algorithms (traces vs windows) across two different hyperparameters, especially with how $m$ and $\\lambda$ are lined up. Although the authors should note how they are doing this (it seems they are using the relation $m = 1/(1-\\lambda)$, but it should be explained in the paper).\n\n**Weaknesses**\n- One limitation is that, despite the authors’ proof that memory traces are usually injective, the exponential decay of the traces will squash most useful information after more than a few time steps. This can be seen clearly in Figure 2, where even in a low-dimensional setting with just $\\lambda = 0.7$, the points become very hard to distinguish. It is not clear to me that a function approximator would be able to meaningfully disentangle these histories without extreme overfitting.\n- It would be nice to see a comparison on harder, more partially observable environments. Would this scale, e.g., with image-based observations? The exponential average would smear moving or appearing/vanishing objects across the frame, and it is not clear to me if this would be useful or distracting to the agent.\n- I am confused by the decision to define sample efficiency in terms of the minimum-achievable value error, $\\min \\bar{VE}_\\mathcal{E}$. Just because this value is lower does not mean that learning requires fewer samples, does it? For example, intuitively, I would think that a linear function does not have a low VE but would be easier to learn because it is convex.", "other_comments_or_suggestions": "- Typo in TLDR of paper: “We analyze the effectiveness of eligibility traces when used as memory a memory in POMDPs.”\n- Viewing Figure 6 causes my computer to lag significantly, for some reason.\n- Y-axis in Figure 5 is misleading, since it doesn’t start at 0. It exaggerates the difference between methods.\n- Typo: “A large $\\lambda$ can then reduces” (line 358).\n- Proof of theorem 5.8 is only partial; it should be called a sketch.\n- Several parts of the paper use “cf.” to refer to a figure or a lemma, but “see” would be more accurate in these instances.\n- The proof of lemma 5.4 doesn’t seem necessary in the main paper. It takes up an entire page, but doesn’t appear to be a central result to the paper’s story. The space could be used to better explain the experiments in Section 5, for instance.\n- Notation $VE_\\mathcal{E}$, where $\\mathcal{E}$ means environment, seems incomplete. Doesn’t the minimum-achievable VE also depend on the policy, $\\pi$?\n- Why is the reward function defined in terms of observations instead of states? This doesn’t seem to match standard POMDP formulations, which define the reward based on the underlying state.", "questions_for_authors": "- Does the lack of injective guarantees for infinite memory traces limit the applicability of memory traces to continuing (i.e., non-episodic) environments?\n- ~“Thus, there exists no environment where windows outperform memory traces in general.” But is the reverse not true, i.e., traces cannot outperform windows, either? Consider a fully observable POMDP where $O_t = S_t$ always. Then wouldn’t a fixed window of $m=1$ be much easier to learn than the exponential average, which smears irrelevant information across time steps?~", "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": "", "extra_scores": {}}, {"review_id": "jwDiaw8lej", "reviewer": "Reviewer_iWAi", "summary": "The paper studies learning with memory traces as an alternative to finite length history windows to solve POMDPs. Memory traces are exponential moving average of observations. In offline RL, when the forgetting factor \\lambda < 0.5, they are shown to be equivalent to learning with windows in capacity and sample complexity. If lambda is larger, they are significantly more efficient. The paper also shows that the memory traces can be easily incorporated into online RL algorithms and outperforms the windows approach.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you very much for your positive review! Below, we respond to your critical points and questions.\n\n> Larger experimental domains would make the paper more attractive.\n\nIndeed, the environments we consider in our experiments are more illustrative than realistic. We intend the main contributions of this paper to be theoretical, and we are working on a follow-up project in which we investigate memory traces empirically in more complex environments. The reason for this is that a more thorough empirical evaluation requires a lot more work. For example, the assumption of one-hot observation only makes sense in small tabular POMDPs. A proper treatment of these issues therefore goes beyond the scope of this paper.\n\n> It appears that the effectiveness of the method relative to the windows method depends on the value of the forgetting factor. What determines the forgetting factor itself? Under what conditions do we need a forgetting factor > 1/2?\n\nThese are interesting questions that we do not yet know the answers to. All that our theoretical (and empirical) results suggest is that $\\lambda$ should usually be larger than $\\frac{1}{2}$, as otherwise a window could be used instead. In our follow-up work, we investigate whether it is possible to learn $\\lambda$, and if there is a way to connect properties of the transition and emission dynamics of the POMDP to the optimal choice for $\\lambda$.", "claims_and_evidence": "The claims are well supported by theorems and proofs. The empirical performance of the memory traces approach is illustrated in Sutton's random walk experiment and in a Minigrid version of T-maze.", "methods_and_evaluation_criteria": "The paper's main contributions are theoretical in nature. The key result that the memory traces are injective if lambda is rational is surprising. The sample complexity results are carefully proved using relevant mathematical machinery, e.g., Kirszbraun's theorem. \nThe experimental results are based on relatively small domains and are proof-of-concept variety. Larger experimental domains would make the paper more attractive.", "theoretical_claims": "I have checked the proofs in the main paper but not those in the Appendix. The main proofs appear to be correct.", "experimental_designs_or_analyses": "The experimental results on the random walk domains and the T-maze domain validate the claims but are relatively small. The authors are encouraged to consider more complex and compelling experiments.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "The paper cites all relevant prior work to the best of my knowledge.", "other_strengths_and_weaknesses": "The paper's theoretical claims and proofs make a strong contribution to the theory of POMDPs. The paper also offers empirical evaluations in multiple domains, but these results are preliminary and can be strengthened.", "other_comments_or_suggestions": "The paper is well written in spite of its highly theoretical content.", "questions_for_authors": "It appears that the effectiveness of the method relative to the windows method depends on the value of the forgetting factor. What determines the forgetting factor itself? Under what conditions do we need a forgetting factor > 1/2?", "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": "", "extra_scores": {"ethical_review_concerns": "================= Post-Rebuttal Update =================\n\nThank you for the responses to the reviews. I stand by my evaluation and think that the paper should be accepted."}}, {"review_id": "4pargboNvV", "reviewer": "Reviewer_hzft", "summary": "This paper addresses the problem of history summarization in POMDPs. Specifically, it proposes a new method to summarize the history with memory traces, which inspired by eligibility traces, in place of the ubiquitous finite-length window. Memory traces induce a representation that accounts for the whole history of observations with exponential discounting of the past. The paper first studies conditions for which the memory trace is an injective function of the history through an original geometric perspective. Then, it compares the properties of memory traces, namely estimation error and complexity, against finite windows in the problem of offline on-policy evaluation, showing that memory traces are competitive with windows when the forgetting is fast and potentially better than windows when the forgetting is slow. Finally, it provides an empirical evaluation in both a toy domain and an illustrative deep RL benchmark to back up the theory.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you very much for your positive review! Below, we respond to your critical points and questions.\n\n**Expanding the discussion on connections to prior work on POMDPs.**\nWe agree that our discussion on related works is relatively sparse. Based on your suggestions, as well as the other reviewers' suggestions, we will expand this section with a discussion on connections to existing empirical work that focuses on using RNNs and transformers for reinforcement learning in POMDPs.\n\n**Why is the reward signal a function of the observations and not of the states?**\nThese two descriptions of POMDPs are equivalent. Given a POMDP with state space $\\mathcal X$, observation space $\\mathcal Y$, set of possible rewards $\\mathcal R$, emission probabilities $p(y \\mid x)$, and state-reward function $r: \\mathcal X \\to \\mathcal R$, we can consider the equivalent POMDP with observation space $\\tilde{\\mathcal Y} = \\mathcal Y \\times \\mathcal R$, emission probabilities $p(\\tilde y = (y, r) \\mid x) = p(y \\mid x)[r = r(x)]$, and observation-reward function $\\tilde r(\\tilde y = (y, r)) = r$. \nWe use the observation-reward definition because it emphasizes that rewards are also quantities that are observed by the agent. In this model, state and reward are conditionally independent given the observation. With the state-reward definition this is not the case, so rewards would technically need to be included explicitly in memory as they could also give information about the state. We are open to changing our definition if it is confusing.\n\n**Why is the policy Markovian?**\nIf the policy $\\pi$ is Markovian, then the combination of POMDP and $\\pi$ describe a hidden Markov model with the same state space $\\mathcal X$ as the POMDP. If the policy is not Markovian, then this is no longer true. However, this is irrelevant to our paper, and so we will change the definition in the final version as follows. Consider the general setup consisting of a POMDP with state space $\\mathcal X$, observation space $\\mathcal Y$, action space $\\mathcal U$, transition dynamics $p(x_{t + 1}\\mid x_t, u_t)$ and emission probabilities $p(y_t\\mid x_t)$, and a general agent with agent state space $\\mathcal Z$, agent state update probabilities $\\pi(z_{t+1}\\mid z_t, y_{t+1})$ and policy $\\pi(u_t\\mid z_t)$. Together, these describe a hidden Markov model with state space $\\Psi = \\mathcal X \\times \\mathcal Z$, observation space $\\mathcal Y$, transition dynamics\n$$p(\\psi_{t+1} = (x_{t + 1}, z_t) \\mid \\psi_{t} = (x_{t}, z_{t-1})) = \\sum_{y_t}p(y_t\\mid x_t)\\pi(z_t\\mid z_{t - 1}, y_t)\\sum_{u_t}\\pi(u_t\\mid x_t)p(x_{t + 1}\\mid x_t, u_t),$$\nand emission probabilities\n$$p(y_t\\mid \\psi_t = (x_t, z_{t-1})) = p(y_t\\mid x_t).$$\nThus, as none of our results depend on the state space of the HMM, this definition shows that our results also apply with non-Markovian policies.\n\n**Are there any structural assumptions on the POMDP for which one or the other is preferable instead?**\nThis is an interesting question that we do not yet know the answer to. Our theoretical results suggest that it is always possible to use memory traces and perform at least as well as the best window-based approach. However, this is only true for the optimal choice of $\\lambda$, which in general will not be known. We are interested in investigating if there is a way to connect properties of the transition and emission dynamics of the POMDP to the optimal choice for $\\lambda$.\n\n**If $\\lambda > 1/2$, are there environments where windows outperform memory traces?**\nYes, there are (e.g., see example A.1). However, there is a \"simple fix\": just choose a different $\\lambda$. If $\\lambda$ is set to a value less than $1/2$, Theorem 5.5 guarantees that no window will outperform the memory trace. The T-maze, which we analyze in Theorem 5.8, is qualitatively different: there is no \"simple fix\" to make a window-based approach efficient here (e.g., by choosing a different $m$). Thus, there is no environment where a window-based approach outperforms memory traces for all $\\lambda$. However, there are environments where a memory trace approach outperforms windows for all $m$ (e.g., the T-maze).\n\n**Other suggestions.**\nThank you very much for your additional suggestions. We are working on a follow-up project right now, and will have a look at your references on RL with trajectory-dependent objectives. We are also examining if it is possible to learn $\\lambda$ online.", "claims_and_evidence": "The claims are supported by theoretical derivations and a brief empirical analysis.", "methods_and_evaluation_criteria": "Comparing the properties of different history summarization techniques in terms of policy evaluation makes sense. The choice empirical domains also fits the theoretical/conceptual nature of the work.", "theoretical_claims": "I only checked (briefly) the proofs reported in the main text.", "experimental_designs_or_analyses": "The experiments are conducted in simple domains, for which the considered design makes sense.", "relation_to_broader_scientific_literature": "To the best of my knowledge, the reported study is original and novel. Most of the (recent) theoretical literature on POMDPs focuses on structural assumptions on the emission functions that makes learning (with a window) statistically tractable. The study of this paper is mostly orthogonal to those results. In terms of methodology, I am not aware of previous works employing this kind of eligibility traces, although I am not familiar with methodological research in POMDPs.", "essential_references_not_discussed": "The paper reports only a few references of a very large body of work on POMDPs. While a broader account of previous POMDP literature would be nice, I am not aware of any critical reference that should be discussed. The method is remarkably simple and I would not be surprised if someone came up with a similar ideas in prior works. There is a lot of works on eligibility traces in POMDP, but hard to tell whether they are related at all. I am more confident on the novelty of the reported analysis, as it employs arguments and techniques that I did not see in prior works.", "other_strengths_and_weaknesses": "Strengths\n- Simple yet clever method for history summarization in POMDPs.\n- Original arguments and techniques;\n- Clear presentation of the ideas and compelling analysis.\n\nWeaknesses\n\nWhile I could not spot any major weakness in the work, my feeling is that more effort could have been made to connect the reported results to the literature of POMDPs (theoretical and empirical).", "other_comments_or_suggestions": "The work is really nice and original! I am happy to propose accepting it for the conference. The underlying idea is simple and compelling, well explained and analyzed with a fresh eye and original techniques.\nI think it could be made an even stronger work by including:\n- A more detailed account of how the presented results relate to recent theoretical advancements in POMDPs, e.g., under which structural properties on the emission function learning in POMDP with memory traces is nearly optimal;\n- A more detailed account of what the study suggests for POMDP practitioners. Practical methods include various approaches for handling long-term dependencies in the history, such as LSTM/GRU architectures (e.g., Hausknecht & Stone 2015 \"Deep recurrent Q-learning for POMDPs\"), history summarization with VAEs (like Dreamer, Hafner et al 2023 \"Mastering diverse domains through world models\"), transformers (Parisotto et al 2019 \"Stabilizing transformers for reinforcement learning\"). How does memory traces findings connect to those? Any rpactical takeaway from the analysis?\n\nAn interesting aspect that is not touched in the paper is the following: Memory traces have a continuous hyper-parameter lambda, which seems easier to optimize from data online w.r.t. the size of the window. Especially, estimating the gradient of an \"hyper-policy over lambda\" looks doable...\n\nMemory traces may have another interesting use other than (general) POMDPs, such as RL with trajectory-dependent objectives: See Hazan et al 2019 \"Provably efficient maximum entropy exploration\", Chatterji et al \"On the theory of reinforcement learning with once-per-episode feedback\", Mutti et 2023 \"Convex reinforcement learning in finite trials\", Kausik et al 2024 \"A theoretical framework for partially observed reward-states in RLHF\" among others.", "questions_for_authors": "Rewards depend on observations instead of states? Also, why the policy is Markovian and conditioned on true states!?\n\nThe paragraph between lines 55-65 (right) is somewhat confusing. The reward is defined as a function from observations to reals, but in POMDP the reward is typically a function from states to reals. Perhaps is a typo there, or the authors mean a function of history of observations? Also, why the policy is a function between states and probability over actions? In POMDPs one typically considers functions from history of observations to actions...\n\nThe lines 281-283 read \"Thus, there exists no environment where windows outperforms memory traces in general\". Are there any structural assumptions on the POMDP for which one or the other is preferable instead?\n\nIn spirit, the results are saying: With $\\lambda < 1/2$ windows and memory traces are on par. With $\\lambda > 1/2$, there exist environments where traces outperform windows. The latter does not exclude the existence of environments where windows are better in the $\\lambda > 1/2$ regime, or am I missing some nuances?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Thanks to some useful back and forth between the reviews and the authors, there is convergence on a positive recommendation for this paper based upon its novel use of an eligibility-trace like concept for memory. The only lingering disappointment is that more ambitious experiments are relegated to future work. This is somewhat relatable given the resources required to do thorough experimentation, but also somewhat unsatisfying.
Decision: Accept (poster)