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.
-
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.
-
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”.
-
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.