acceptodds
Under review as a conference paper at ICLR 2027

Retracing the -Discrepancy: Memory Learning from Off-Policy Data

Abstract

Acting optimally under partial observability requires memory. Allen et al. (2024) recently proposed to use the -discrepancy, defined as the gap between value estimates obtained at different bootstrapping horizons, as a model-free signal for learning memories that disambiguate latent states. However, the on-policy formulation limits its applicability when fresh interaction data is expensive. Extending the -discrepancy to off-policy learning is nontrivial. When trajectories are generated by a different policy, the resulting multi-step returns no longer correspond to those of the target policy. Importance sampling can correct this mismatch, but often at the cost of prohibitively high variance. We overcome these issues by introducing the Retrace discrepancy, an off-policy generalisation of the -discrepancy built from Retrace-style trace corrections (Munos et al., 2016). We first show that the corresponding Retrace operator admits a unique fixed point even without assuming that the observations are Markovian. We then prove that the resulting discrepancy preserves the key partial-observability detection property of the original -discrepancy: if a POMDP has a nonzero on-policy -discrepancy for some policy, then, for almost every combination of behaviour and target policy in the off-policy setting, the Retrace discrepancy is nonzero as well. Experiments demonstrate partial-observability detection and memory learning from replay. On Battleship and Minesweeper, the replay-trained agent first exceeds selected mean-return thresholds with 4.4x and 3.0x fewer environment interactions, respectively, than PPO with the on-policy -discrepancy.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, Partially observable MDPs, Off-policy learning, Memory learning, Retrace

Reviews

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

Earlier work of Allen et al. (2024) introduced the so-called lambda-discrepancy as a one-sided diagnostic of inconsistent value prediction under insufficient memory in a POMDP. The measure is based on comparing two Q functions computed with multi-step temporal-difference learning of different trace parameters. The central issue that the paper addresses, is that in an off-policy setting, multi-step temporal-difference learning requires corrections, such as importance sampling, tree-backup, or retrace, all proposed in earlier works. The paper establishes that the lambda-discrepancy from Allen et. al. (2024) with retrace corrections and off-policy learning provides a one-sided diagnostic of inconsistent value prediction in POMDPs, thereby generalizing the result form Allen et. al. (2024) from on-policy to off policy.

Critical strengths

The writing is clear and the mathematical statements appear to be correct. Proofs have not been checked line by line, however.

Critical weaknesses

The algorithmic contributions are somewhat limited: lambda-discrepancy has been introduced before, the issue with multi-step temporal-difference learning in off-policy settings are known, and the retrace correction has also been introduced before (Munos, 2016). Nonetheless the detection theorem (Theorem 3) appears to be a nontrivial extension from the literature, e.g., due to the fact that there is a clipping operation.

My main concern is the connection between detection and memory learning. Nonzero exact discrepancy witnesses insufficient observations, but zero discrepancy does not certify sufficiency, and its magnitude need not rank memory representations by predictive or control quality. The authors acknowledge this limitation and illustrate nonmonotonicity in Figure 6. Consequently, the detection results alone do not establish that minimizing the proposed objective improves memory. The learning experiments provide empirical support, but further analysis would help explain when and why this objective is effective.

In particular, a systematic study varying history-window length or memory representation, and reporting lambda-discrepancy alongside prediction error and control return, would further clarify the relationship between the proposed diagnostic and a useful signal for memory learning.

Questions for authors

Can you isolate the contribution of the discrepancy loss? Please provide an ablation retaining both auxiliary retrace critics and their regression losses in (10) while disabling the discrepancy loss. This would help isolate the benefit of discrepancy minimization.

Can you extend Figure 6’s analysis to controlled memory representations or history-window lengths on the learning benchmarks? In particular the non-monotonicity of the discrepancy-measure is concerning.

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

This paper follows up the prior work of Allen et al, propose a similar mechanism to mitigate the partial observability by learning a Markov state-representation. Like soft actor critic (SAC) improves the sample efficiency of PPO, their proposed framework can work with off-policy partially observable deep RL algorithm. The theoretical framework justifies the proposed lambda discrepancy estimator to satisfy basic properties useful to detect non-Markovian representation. Numerical experiments on several small-scale tasks validate the effectiveness of the proposed method.

Critical strengths

The story is clear and the theory looks valid to me. I appreciate the details provided in the appendix which is both rigorous and helps understanding. The Parity Check example in Figure 1 is particularly interesting that it solves something that is not differentiable with on policy λ\lambda-discrepancy.

Critical weaknesses

If the reader is not very familiar with the Allen et al. paper, then the writing might be hard to understand. Especially the notations used to define the key terms in the paper, why in theory it only depends on observation w and in implementation it depends on memory mm (see questions for details). But this is fixable in my opinion. The key problem is the insufficient experiments. Current experiments are either on toy example or small-scale games, and the advantage is not clear compared to vanilla deep RL implementation such as AC. It is well-known that SAC achieves better results than PPO on many locomotion tasks. as stated in the limitation, it would strengthen the paper if more experiments on broader tasks like Crafter, Maze and locomotion are provided.

Questions for authors
  1. line 173, what do you mean "Both policies"?, why the policy only depend on the observation? how to understand the policy space definition ∏w\prod_w?
  2. about modeling in (3), justify why q function only depends on observation w and action a, independent of the memory m or all previous actions; why this is a useful formulation to define the value function under partial observability.
  3. In figure 3, λ1\lambda_1 head and λ2\lambda_2 head use mtm_t as input, it is confusing given the above formulation.
  4. Compare Figure 4 and Figure 11, PPO + λ\lambda achieves similar performance as AC + Retrace in about the same steps? And PPO+λ\lambda achieves higher ending score. For a paper claiming sample efficiency why not compare them directly in the same figure in the main text?
  5. In the minesweeper task, Figure 12, the advantage of AC + Retrace compared to Recurrent AC is almost negligible, makes one question if the λ\lambda discrepancy actually works. Figure 11 and 13 are good examples of a clear edge.
Reviewer_NjuyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper essentially extends the work of Allen et al.[1] to the off policy setting by introducing Retrace discrepancy, which compares the fixed point of the Retrace operators at two different trace parameters for a fixed behavorial policy and target policy. The paper defines the retrace operator on observations that could be non-Markovian, and shows that it is a γ\gamma-contraction with a unique fixed point, and also shows that the discrepancy is zero if the observations are Markov-sufficient. The paper shows that if a policy has nonzero on-policy λ\lambda-discrepancy, then the Retrace discrepancy is also nonzero for almost every pair of behavior, target policy. The work validates the claims experimentally, and show the exact and finite data detection in T-maze, where neural critics recover the off-policy signal from replay, and shows results for a recurrrent actor-critic with two auxillary retrace heads evaluated on the Battleship and Minessweeper environments.

[1] Allen, Cameron, et al. "Mitigating partial observability in sequential decision processes via the lambda discrepancy." Advances in Neural Information Processing Systems 37 (2024): 62988-63028.

Critical strengths

The paper idenitfies and motivates on-policy data collection as a practical problem in λ\lambda-discrepancy, and the trade-off with importance sampling is well stated. The theoretical work in the paper is novel and seems correct (all though I did not check appendix very thoroughly). In appendix A.6, the authors state very clearly state what is not guaranteed, the limitations are very clearly stated with counterexamples. The authors also provide the necessary information to reproduce the experiments.

Critical weaknesses

w1: One of the main claims of the paper is that retrace discrepancy improves sample efficiency, but the ratio in the experiments compares AC+retrace with PPO+λ\lambda, and the results only support that replay is more efficient than PPO, which is well known.

w2: The experiments are done on toy environments, also the paper doesn't mention why the original 10x10 Battleship used in Allen et al.[1] was changed to 5x5 (in Appendix F2).

w3: There are a few discrepancies between the theory and the algorithm, for example the experiments use unfirom replay sampling for both Minesweeper and Battleship, but Theorem 3 assumes discounted occupancy posterior in equations 29-33.

w4: Minor notation issues with α\alpha, not clearly defined in the main text.

[1]Allen, Cameron, et al. "Mitigating partial observability in sequential decision processes via the lambda discrepancy." Advances in Neural Information Processing Systems 37 (2024): 62988-63028.

Questions for authors

q1: Related to w1, can you report the TrecurrentAC(r)T_{recurrentAC}(r) (recurrent AC baseline) to TAC+retrace(r)T_{AC+retrace}(r) in the results like Fig 4b? Maybe plotting this is a better proof of the effect of retrace discrepancy.

q2: Can you compare your results with the uncorrected replay λ\lambda-discrepancy, and also the importance sampling-corrected one?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.