acceptodds
Withdrawn from ICLR 2027

Beyond K-step Histories: Learning to Remember Reward Relevant Observations for Non-Markovian RL

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Reinforcement learning with partial observations can require retaining information across long temporal delays, even in controlled environments. We study how computationally limited agents can manage this information when only a small subset of past observations is relevant for decision-making. The predominant approach, sliding windows (also called frame stacking), maintains a window (stack) of the most recent observations, but the required stack size grows with the degree of non-Markovian dependencies, leading to prohibitive computational and memory requirements for both inference and learning. We build on the observation that many environments that are highly non-Markovian over time depend causally on only a small subset of past observations. This motivates meta-algorithms that maintain small adaptive memory stacks, enabling the representation of long-term dependencies while processing fewer observations per step. We propose Adaptive Stacking, a meta-algorithm with convergence guarantees, and quantify its computational and memory savings for MLP, LSTM, and Transformer-based agents. Using controlled memory tasks with varying degrees of non-Markov dependencies, we show that Adaptive Stacking learns to discard memories that are not predictive of future rewards while retaining important experiences.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Non-Markovian, Partial Observation, State abstraction, Bounded Agents, Memory

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_3rM3OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes an alternative to frame stacking, called adaptive stacking (AS) where the agent stores a stack of observations, and at each step outputs both an environment action and a memory action which chooses a stack element to remove before a new observation is added. The goal is to solve the problem in non-Makrovian environments where frame stacking would need a stack that grows exponentially with the length of dependencies. They define the smallest memory size the agent needs to actually optimally and prove under certain assumptions the standard RL algorithms still converge to an optimal policy when the agent learns what to store in that memory. They validate the claims experimentally on small domains and compare it with frame stacking.

Critical strengths

The problem statement in the paper is well motivated, and there is a gap between the markov order k* and the number of actual relevant observations, as sparse long range dependencies are quite common in non-Markovian processes. The experiments are quite broad and the results are interesting, and provide strong evidence that their approach learns the intended memory policy. The motivation for the theory in the main text seems correct, and the contribution seems novel, though incremental.

Critical weaknesses

w1: the TD/Q learning guarantees rely on the assumption that all histories that produce the same memory contents must have the same value, but this doesn't hold for T-maze, because with discounting the same memory can refer to being different number of steps away from the goal and that would have different values. So the guarantees won't apply to T-maze in this case, and quite possibly the other cases as well.

w2: Related to w1, the authors claim that AS goes beyond standard value preserving abreaction, but the assumption states the opposite, so in the case where the values are wrong but the policy is still optimal has no guarantees.

w3: The work seems very similar to the setting of Icarte et al. [1] which the authors do not cite, and the novelty of this paper seems very limited.

w4: In Appendix C.5, line 1262, it says "I sketched the standard way to satisfy this...", can't be sure but this seems like a part of an LLM response. Also the paper does not have the required AI use statement.

[1] Icarte, Rodrigo Toro, et al. "The act of remembering: A study in partially observable reinforcement learning." arXiv preprint arXiv:2010.01753 (2020).

Questions for authors

Can you elaborate more on how your method is different from Icarte et al.? See w3.

Reviewer_tJCEOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes Adaptive Stacking (AS): the agent maintains a stack of k past observations, with the last slot always the current observation, and, along with its environment action, chooses which slot to evict (including the current one), rather than the FIFO eviction used in Frame Stacking (FS). It defines k* (the policy-independent order of the environment) and κ (the smallest stack size for which some AS policy is optimal), and argues that AS gives Ω(k*/κ) savings in compute and memory for MLP, LSTM, and Transformer policies.

The theoretical claims are: (i) any algorithm with unbiased value estimates that converges under FS with k ≥ k* also converges to an optimal policy under AS with k ≥ κ (Theorem 4.4, Corollaries C.4–C.5); (ii) under a value-consistency assumption (Assumption 4.5) the ordering of policies is preserved by the abstraction (Theorem 4.6), so TD learning and Q-learning also converge to optimal policies (Theorem C.8).

Empirically, AS(κ) is compared with FS(κ) and an “oracle” FS(k*) on Passive/Active T-Mazes (tabular Q-learning; PPO with MLP, LSTM and Transformer policies), XorMaze, a 2×2 Rubik’s cube, MiniGrid-Memory and a partially observable FetchReach. AS(κ) is reported to match the oracle, use far less memory, and generalize to mazes of length 10^6 after training on length 16.

Critical strengths
  • The problem is important and well motivated: learning what to retain under a fixed memory budget, from reward alone, is the right question for bounded agents in long-horizon partially observable environments.

  • Letting the agent evict any slot (rather than push/skip with FIFO eviction) is a real, if small, generalisation of earlier memory-action schemes, and the XorMaze (App. F.4) is a convincing example where it matters.

  • The memory-regret metrics (active vs. passive) are a useful diagnostic for this family of methods.

  • Remark 4.1 (a value gap need not imply a policy gap) is correct and worth stating explicitly, and the compute/memory accounting in App. G is careful.

  • The out-of-distribution evaluation on maze length and grid size is a good idea, and the experiments span several learners (tabular Q-learning, PPO, a critic-free MC variant) and architectures (MLP, LSTM, Transformer), with hyperparameters reported.

Critical weaknesses

W1. Theorem 4.4 and Corollaries C.4–C.5 do not hold: the argument is circular, and there is a counterexample

Why the proof does not go through. Assumption C.2 assumes that, for every memory length k, A converges to the global argmax over k-order policies of an unbiased return estimate. With that assumption, Theorem C.3 is immediate from the definition of κ. The content therefore rests on step 4 of the proof of Corollary C.4 (“because REINFORCE provides unbiased estimates … the Unbiased Convergence Assumption is satisfied”). Unbiased gradient estimates give convergence to stationary points of J, not to its global maximum, and J on the induced process M_k is not concave: by Eq. (2), V_k^{π}(s_t) = Σ_x Pr(x | s_t, π) V^{π}(x), and the aliasing weights Pr(x | s_t, π) depend on the policy. This is the classical setting of memoryless policies in POMDPs (Singh et al., 1994; Littman, 1994; Jaakkola et al., 1995), where only local convergence is available; the paper applies a global claim to exactly this setting.

The counterexample, intuitively. Take the paper’s Passive-T-Maze and paint the corridor. At the entrance, the agent sees the cue, A or B. Each corridor cell then shows a color that is usually the opposite of the cue (with probability 1 − ρ) and occasionally the same color (with probability ρ). At the junction, the agent must turn to the side that matches the cue (reward +1 if it does, −1 otherwise). Its memory is a two-slot stack: one slot it controls, plus the current observation. There are two self-consistent ways to use this memory:

  • Remember. Put the cue in the slot at the entrance and never let the corridor overwrite it; at the junction read the slot and turn to the matching side. Always right: value 1.
  • Overwrite and invert. Let the corridor overwrite the slot at every step, which is exactly what Frame Stacking does, so that at the junction the slot holds the last corridor color; then turn to the side opposite to that color. Right whenever the last corridor cell was anti-correlated with the cue (i.e., with probability 1 − ρ): value 1 − 2ρ.

We ran this example under ideal conditions, and AS converges to the suboptimal convention. Concretely: m = 2 corridor cells and ρ = 0.1, so k* = 4 (the maze is passive, so this is the policy-independent k* of Section 2) and κ = 2; the stack mechanics of Section 4.1 and the two-head softmax policy of App. E.4, tabular over stack states (maximally expressive); and, instead of sampled returns, the exact policy gradient computed by dynamic programming on M_k (the zero-variance limit of REINFORCE, hence unbiased by construction), with uniform initialization. Under FS(k* = 4), the induced process is an MDP and gradient ascent reaches return 1.0. Under AS(κ = 2) it converges to return 0.8 = 1 − 2ρ, the Overwrite-and-invert policy, which is exactly the optimum of FS(κ): the memory actions are never used. AS(k* = 4) also reaches 1.0. The paper’s own learners behave the same way: REINFORCE with annealed entropy and projection (the setting of Corollary C.4) gives 0.797 vs. 0.994 for FS(k*), and tabular Q-learning (Algorithm 1) gives 0.8 in every seed. The trap persists for ρ up to 1/3 (m = 2) or 3/7 (m = 3), and 55–85 % of random initializations end in it as well.

Why this happens. Learning starts with random memory decisions, so at the junction the slot almost always holds the last corridor color rather than the cue (the cue survives m random evictions with probability 2^{−m}). The first thing the junction learns is therefore “turn opposite to the slot color”. Once it does, remembering the cue is harmful (a remembered A is read as “turn right”), so the memory policy learns to discard it; and once the cue is discarded, inverting is the only rule consistent with what is retained. Each half of the policy is now the best response to the other, and every unilateral change is punished: at the converged policy all first-order advantages are ≤ 0, no nearby policy improves J, and the return along the straight path to the optimal policy drops to ≈ 0 before rising to 1. In the language of Eq. (2), the aliasing weights Pr(x | s_t, π) depend on the policy, so J is not concave on M_k and unbiased gradients only find a local maximum, exactly as for memoryless policies in POMDPs (Singh et al., 1994; Jaakkola et al., 1995). Unbiasedness plays no role here, since the gradient was exact. (The trap relies on the stack storing observations without their time index, as in the paper’s own T-Maze and in its continual setting; with time-stamped observations, this particular trap disappears.)

Consequence. Theorem 4.4, Corollaries C.4–C.5, the abstract (“a meta-algorithm with convergence guarantees”) and contribution 2 in Section 1 (“guaranteed to converge to an optimal policy in general when using unbiased value estimates”) must be withdrawn or restated as a local result in the style of Jaakkola et al. (1995), with Assumption C.2 named for what it is: a global-optimality assumption that unbiasedness does not imply.

W2. Assumption 4.5, Theorem 4.6 and Theorem C.8 give no learning guarantee

Put plainly, Assumption 4.5 says: under policy π, all the histories that the stack lumps into the same state s are worth the same, so the abstract value V_k^{π}(s) is exact. It is a property of a policy, not of a task, and the three results built on it reduce to it.

  1. Theorem 4.6 restates the assumption. If the abstract values of two policies are both exact, comparing them is comparing true values; that is the definition, not a theorem. The sentence drawn from it (“any RL algorithm that converges to the optimal policy under Adaptive Stacking simultaneously converges to the optimal policy over the underlying history”) is Definition 4.2. The hard part, that a learner reaches the AS-optimal policy at all, is never addressed.

  2. The assumption excludes the policies a learner must pass through, and fails even for π* in the paper’s own example. To cover a learner, Assumption 4.5 must hold for every policy along its trajectory. With κ < k* it fails as soon as a policy discards something relevant, which is exactly what AS has to learn not to do: in the paper’s own T-Maze with k = 2, a policy that forgot the cue and turns left with probability p lumps histories worth 2p − 1 and 1 − 2p into the same stack [grey, J]. Even the optimal policy violates it in Section 4.1’s worked example, where the stack [G, grey] lumps histories worth γ³, γ², and γ, which differ whenever γ < 1 (the experiments use γ = 0.99). Table 2’s “✓: only goal cue matters” and the claim that the assumption “happens to always hold for … goal-reaching tasks” are therefore incorrect under the paper’s own definition; what Table 2 actually checks is Remark 4.1 (the optimal action depends only on the retained cue), a much weaker property for which the paper itself notes that TD convergence “cannot be shown”.

  3. The TD and Q-learning claims are unsupported. The paper makes two claims. (a) After Theorem 4.6: TD(0) converges to a fixed point that is “generally lower than the true expected return”, “hence TD-learning also preserves partial-ordering”. (b) Theorem C.8: under a fixed exploratory policy, Q-learning converges, and the greedy policy of its fixed point is optimal. Both cite Singh et al. (1994), which says neither. Its Theorem 1 states only that the TD(0) fixed point differs from the true value, with no direction (in its Figure 2 the fixed point is below the true value for one observation and above it for another), and its Facts 5–6 show that in a POMDP policies cannot in general be ordered observation by observation, so there is no ordering to preserve. Its Theorem 2 does give the convergence of Q under a fixed exploratory policy, but the same paper then says that this fixed point “suffers from the same problem” and conjectures that Q-learning “will not find the best deterministic memory-less policy”, the opposite of what C.8 concludes; the proof of C.8 never connects the fixed point to the optimal policy. The counterexample of W1 confirms the gap: running tabular Q-learning (Algorithm 1) with a uniform exploratory policy on the painted T-Maze, the greedy policy of the fixed point is worse than random (returns of −0.01, −1.00 and −0.01 over three seeds, against 1.0 for the optimal policy). Assumption 4.5 does not rescue the claim. In the painted T-Maze it holds for the optimal policy and for the uniform exploratory policy, and the greedy policy of the Q-learning fixed point is still worse than random; read for every policy, it fails there, but then it fails in every task where some policy can forget something that matters, which is exactly the setting AS is for.

What survives of Sections 4.2–4.3 is Proposition 4.3, Remark 4.1 and the known fact that M_k is a POMDP. For the regime the paper advertises, κ ≪ k*, there is no learning guarantee.

W3. Empirical evaluation

The experiments do not establish the generality of “AS(κ) matches the oracle”, and the baselines are either handicapped or mis-described.

  • Baselines and the cost comparison. The LSTM and Transformer agents re-read the k-slot stack at every step (App. E.4); they are not recurrent agents with carried state. For FS(k*) in the episodic Passive-T-Maze, the stack is the whole episode (k* = T), so that baseline is a full-episode LSTM, and it performs on par with AS(κ) (Figs. 10, 25): the finding is parity, not an advantage of AS. The Ω(k*) per-step cost assigned to LSTMs (Table 1, App. A) comes from re-reading the window; a standard recurrent policy carries its state at O(1) per step, and the BPTT truncation length bounds credit assignment, not the memory horizon (Ni et al., 2021, cited but not run). Savings over recurrent agents should be measured against such a policy.
  • Length generalisation holds by construction. FS(16) trained on length 16 fails on length 10^6 (Fig. 1) because a 16-slot stack cannot contain the cue, for the MLP and the Transformer; once AS(κ = 2) retains the cue, its agent state is constant along the corridor, so transfer to any length is automatic. These results illustrate the representation; they are not evidence about learning, and the text should say so rather than “possibly due to overfitting”.
  • Open questions (see Questions 6 and 8). Does the DemirStack baseline see the current observation when it skips? If not, with k = κ it cannot both retain the cue and navigate, which would explain its failures in the Active-T-Maze and XorMaze by construction. At test time on longer mazes, is the FS(k*) stack capped at the training k* or does it grow with the episode? (Figs. 24–26 show FS(k*) at chance out of distribution for the MLP and the Transformer but at 1.0 for the LSTM.)

The painted T-Maze of W1 is a two-line change to the Passive-T-Maze; running it with the paper’s PPO and Q-learning code, with the memory-regret metrics, would settle whether the headline claim is general.

W4. Closely related work is missing

Section 3 names Peshkin et al. (1999) and Demir (2023) as the closest work, but Toro Icarte et al., “The act of remembering: A study in partially observable reinforcement learning” (arXiv:2010.01753, 2020), is closer and is not cited. That paper already (i) gives a general framework of external memories controlled by memory actions, of which Adaptive Stacking is an instance; (ii) proposes O_k memories, a buffer of past observations with push/skip actions and the current observation always visible to the policy, which is AS with FIFO eviction (with k = κ = 2, the setting of the T-Maze and MiniGrid-Memory experiments, AS is exactly O_1); (iii) shows that the memory-augmented environment is a POMDP and not an MDP, analyses the resulting failure of TD methods and recommends Monte-Carlo or n-step learners, i.e. the content of Sections 4.2–4.3; and (iv) proves in its Appendix C that policy improvement with perfect value estimates converges to a suboptimal policy even with sufficiently expressive memories, the failure mode that Theorem 4.4 claims cannot occur. The paper should discuss this work, state non-FIFO eviction as its delta over O_k, and compare against O_k / OA_k under equal information.

Questions for authors
  1. On Theorem 4.4. Assumption C.2 asks A to reach the global argmax over k-order policies. Is this intended to assume global optimality? If so, which algorithm satisfies it on the POMDP M_k, and why? If not, how does step 4 of the proof of Corollary C.4 (“REINFORCE provides unbiased estimates, hence the assumption is satisfied”) follow, given the counterexample in W1?

  2. A direct check. Could you run the painted T-Maze of W1 (two corridor cells whose color is the opposite of the cue with probability 0.9 and the same color with probability 0.1) with your PPO and Q-learning code, reporting returns and memory regret for AS(κ = 2), FS(κ = 2), and FS(k* = 4)? In my runs AS(κ) stays at the FS(κ) optimum (return 0.8) while FS(k*) reaches 1.0.

  3. On Assumption 4.5. Is it meant only for the optimal policy, or for every policy the learner passes through? Under the first reading, how do Theorems 4.6 and C.8 apply along a learning trajectory, and which result of Singh et al. (1994) supports the claim that TD-learning preserves the ordering of policies? Under the second, in which task of Table 2 does the assumption hold with γ = 0.99, given the value gap computed in Section 4.1?

  4. On the DemirStack baseline (App. F.4). Does the policy receive the current observation when it skips? If not, with k = κ the agent cannot both retain the cue and see where it is, which would explain its failures in the Active-T-Maze and XorMaze by construction. How does AS compare with push/skip when the current observation is available (the O_k memories of Toro Icarte et al., 2020)?

  5. On the sequence-model baselines. At test time on longer mazes (Fig. 1, Figs. 24–26), is the FS(k*) stack capped at the training k* or does it grow with the episode? And could you add a recurrent PPO baseline whose hidden state is carried across BPTT truncation (e.g. the setup of Ni et al., 2021) to the length-scaling and compute comparisons? Without it, the Ω(k*) cost attributed to LSTMs in Table 1 describes re-reading a stack, not a recurrent agent.

Reviewer_ZtgeOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes an approach called Adaptive Stacking, which, unlike Frame Stacking, does not use all consecutive frames but instead allows irrelevant frames to be discarded while retaining only those necessary for solving the task. This reduces working memory requirements, particularly in long-horizon tasks.

Critical strengths

Theoretical justification for the convergence of agents to an optimal policy.

Critical weaknesses
  1. Despite the detailed theoretical analysis and positioning of the proposed method, insufficient space is devoted to describing the method itself, leaving several aspects unclear. In particular, it is unclear how the frame selection mechanism is trained and what limitations and hyperparameters it has.

  2. Only variations of Frame Stacking are used as baselines, without comparisons with more recent models such as FFM [1], SHM [2], and ELMUR [3].

  3. The experimental evaluation is insufficient, as it primarily relies on similar environments. It would be useful to evaluate how the proposed approach performs in environments with different dynamics, for example, on POPGym [4], a standard benchmark for memory in RL. Furthermore, it is not entirely clear whether visual observations are used in MiniGrid-Memory and FetchReach. It is important to evaluate the method on visual observations, for example, using POPGym Arcade [5] or MIKASA-Robo [6], which is more closely related to real-world tasks. It would also be valuable to evaluate the approach in three-dimensional environments conceptually similar to T-Maze, such as VizDoom-Two-Colors [7].

  4. The limitations of the proposed method are also insufficiently investigated. For example, how does the method behave when the relevant information cannot be captured in a single frame and requires tracking an object's motion, as in the Atari example? Another important scenario is when the relevant cue changes its meaning throughout an episode, as in Endless T-Maze [8].

Additional comment: There appears to be a discrepancy between Figure 3 and its description.

References:

  1. Morad, Steven, et al. "Reinforcement learning with fast and forgetful memory." Advances in Neural Information Processing Systems 36 (2023): 72008-72029.
  2. Le, Hung, et al. "Stable hadamard memory: Revitalizing memory-augmented agents for reinforcement learning." International Conference on Learning Representations. Vol. 2025. 2025.
  3. Cherepanov, Egor, Alexey Kovalev, and Aleksandr Panov. "ELMUR: External layer memory with update/rewrite for long-horizon RL problems." International Conference on Learning Representations. Vol. 2026. 2026.
  4. Morad, Steven, et al. "Popgym: Benchmarking partially observable reinforcement learning." arXiv preprint arXiv:2303.01859 (2023).
  5. Wang, Zekang, et al. "Investigating Memory in Model-Free RL with POPGym Arcade." arXiv preprint arXiv:2503.01450 (2025).
  6. Cherepanov, Egor, et al. "Memory, benchmark & robots: A benchmark for solving complex tasks with reinforcement learning." International Conference on Learning Representations. Vol. 2026. 2026.
  7. Sorokin, Artyom, et al. "Explain my surprise: Learning efficient long-term memory by predicting uncertain outcomes." Advances in Neural Information Processing Systems 35 (2022): 36875-36888.
  8. Shchendrigin, Oleg, et al. "Memory retention is not enough to master memory tasks in reinforcement learning." arXiv preprint arXiv:2601.15086 (2026).
Questions for authors

What hyperparameters does the proposed method have? Have any ablation studies been conducted to assess their impact?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.