acceptodds
Under review as a conference paper at ICLR 2027

Reward-Agnostic Replay for Shared-Structure Policy Evaluation

Abstract

How should stored transitions be prioritized when the same experience supports predictions of multiple signals? We study reward-agnostic replay for linear temporal-difference (TD) policy evaluation with a replay buffer. We exploit the decomposition of the expected TD update into a matrix shared across reward functions and a reward-dependent vector. By formulating estimation of the shared matrix as an approximate matrix multiplication problem, we derive a replay rule that prioritizes transitions using the product of the current-state feature norm and the norm of its discounted one-step feature difference. For the corresponding unbiased matrix estimator, this sampling rule minimizes expected squared Frobenius error within the estimator family we consider. The priorities are reward-independent, so they can be reused across multiple reward functions, including reward functions introduced later, without any reward-specific recomputation. In multi-reward evaluation with the reward-dependent vectors computed from the full buffer, a single norm-sampled matrix estimate improves value prediction over uniform replay and eventually outperforms reward-dependent PER as the number of tasks grows. The same priorities also transfer to held-out tasks and to tasks introduced later. Finally, we apply the same sampling rule to DQN on four MinAtar games, where we observe game-dependent gains in return and lower auxiliary multi-signal Bellman residuals in several settings. Together, these results help characterize when shared, reward-independent structure is useful for replay prioritization.

Primary area:
reinforcement learning
Keywords:
reinforcement learning

Reviews

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

This paper introduces a reward agnostic replay strategy for linear temporal difference (TD) policy evaluation and general value functions (GVFs). In linear TD and least squares TD (LSTD), the expected update separates into a shared TD matrix AA that depends on the policy, transition dynamics, and feature representation, and a reward dependent vector bb that depends on the reward or cumulant. When multiple predictions share the same policy and features, AA is shared across tasks while each task kk has its own vector bkb_k. By expressing AA and its replay buffer analogue ABA_B as a product of two feature matrices, the authors formulate estimating AA under a limited budget as an approximate matrix multiplication (AMM) problem. This yields a norm based sampling rule that prioritizes each transition ii by the product of the norms of the current state feature ϕi\phi_i and the discounted one step feature difference ψi\psi_i. Within the unbiased AMM estimator family, this rule minimizes the expected squared Frobenius error of the estimate A^\hat{A}. Experiments on a random chain, Four Rooms, and MinAtar DQN show that these reward independent priorities improve value prediction in multi reward evaluation and outperform prioritized experience replay (PER) as the number of tasks KK grows.

Critical strengths

A main strength of the paper is its simple formulation together with its transparent empirical analysis of when reward agnostic replay helps and when it fails. By separating the shared matrix AA from the reward vector bb in LSTD, the proposed norm based priority depends only on the feature vectors ϕi\phi_i and ψi\psi_i, allowing a single replay distribution to be computed once and reused across multiple GVF tasks, held out cumulants, and newly arriving tasks without recomputing TD errors. Moreover, rather than claiming universal gains, the authors provide a clear heterogeneity diagnostic using the coefficient of variation of the priority scores uiu_i to explain when targeted sampling improves over uniform replay, and they include informative ablations on AA and bb that clearly show why reward aware PER remains superior in single task and iterative TD settings where estimation error in b^\hat{b} dominates.

Critical weaknesses
  • The theoretical contribution is rather incremental, as the main proof backbone comes directly from prior literature (Drineas et al., 2006a). In Section 3.1 and Appendix C, Lemma 1 and Lemma 2 are existing AMM results, and the only new step is writing the shared TD matrix AA (or its empirical replay buffer analogue ABA_B) as a sum of per state or per transition rank one outer products so that the AMM variance result applies directly. Beyond this reformulation and a standard deterministic matrix perturbation bound for regularized LSTD in Proposition 1, the paper proves no new statistical property for its sampler, nor does it provide any sample complexity bound or expected value error bound under norm based sampling.
  • The applicability of the theoretical analysis in Proposition 1 and Corollary 2 is limited. First, Proposition 1 assumes an exact, fixed reward vector bb (lines 203 to 204), so it does not apply to single task prediction from a sampled batch or iterative TD updates where b^\hat{b} is also estimated, which are precisely the regimes where norm based replay fails to help empirically. Second, the theory only covers the unbiased inverse probability weighted AMM estimator, whereas the replay buffer experiments use biased estimators with priority exponent α\alpha, importance sampling exponent β\beta, and max normalization, or omit importance sampling correction entirely by setting wj=1w_j = 1 in MinAtar (lines 246 to 248 and 1080 to 1081). Third, the only theoretical link to value error, Proposition 1, requires the Frobenius error between A^\hat{A} and AA to be smaller than σλ\sigma_\lambda, the smallest singular value of A+λIA + \lambda I, yet the paper never analyzes when this condition holds.
Questions for authors

Beyond restating the approximate matrix multiplication result of Drineas et al. (2006a) and a standard perturbation bound for regularized LSTD, can the authors provide a theoretical result specific to the proposed sampler, such as a bound on multi task value error across KK GVF tasks when both A^\hat{A} and b^k\hat{b}_k are estimated, that explains when norm based sampling overtakes reward dependent PER as KK grows and how this depends on the distribution of reward vectors bkb_k?

2 comments
AuthorsOpenReview ↗

Response W1 and Q1

We thank the reviewer for the careful reading, and for noting the simple formulation and the transparent analysis of when reward-agnostic replay helps and when it fails. We respond to the two weaknesses and the question below; we address W1 and Q1 together, as both concern the theoretical contribution.

W1 and Q1. A theoretical result specific to the proposed sampler

We attribute Lemmas 1 and 2 to Drineas et al. (2006) and describe Proposition 1 as standard; we do not claim them as new. The contribution is the reduction: with a shared AA, choosing what to replay becomes an AMM problem with a closed-form, reward-free answer. Following the reviewer's suggestion, we have extended this analysis to characterize the optimal sampler across multiple tasks, both when bkb_k is exact and when it is estimated from the batch (Proposition 3, Appendix E.1, with a pointer from Section 3.2).

Setting. Let θk=(A+λI)−1bk\theta_k=(A+\lambda I)^{-1}b_k and A^=1B∑jϕijψij⊤/(Npij)\hat A=\frac{1}{B}\sum_j \phi_{i_j}\psi_{i_j}^\top/(Np_{i_j}). Then θ^k−θk=−(A^+λI)−1(A^−A)θk\hat\theta_k-\theta_k=-(\hat A+\lambda I)^{-1}(\hat A-A)\theta_k exactly, so the residual (A^−A)θk(\hat A-A)\theta_k is the quantity the sampler controls.

Proposition 3(a) (exact bkb_k). For any sampling distribution pp, 1K∑kE∥(A^−A)θk∥2=1B[1N2∑i∥ϕi∥2ψi⊤Sψipi−1K∑k∥Aθk∥2],S=1K∑kθkθk⊤.\frac{1}{K}\sum_{k}\mathbb{E} \Vert(\hat A-A)\theta_k\Vert^2=\frac{1}{B}\Big[\frac{1}{N^2}\sum_i \frac{\Vert\phi_i\Vert^2 \psi_i^\top S \psi_i}{p_i}-\frac{1}{K}\sum_k\Vert A\theta_k\Vert^2\Big],\qquad S=\frac{1}{K}\sum_k\theta_k\theta_k^\top . It is minimized by pi⋆∝∥ϕi∥ψi⊤Sψip_i^\star\propto\Vert\phi_i\Vert\sqrt{\psi_i^\top S \psi_i}. The norm rule pi∝∥ϕi∥∥ψi∥p_i\propto\Vert\phi_i\Vert\Vert\psi_i\Vert is exactly optimal when S∝IS\propto I; in general, its sampler-dependent term exceeds the optimum by the factor 1+CV2(r)1+\mathrm{CV}^2(r), where ri=ψi⊤Sψi/∥ψi∥r_i=\sqrt{\psi_i^\top S \psi_i}/\Vert\psi_i\Vert and the coefficient of variation is taken under weights ∥ϕi∥∥ψi∥\Vert\phi_i\Vert\Vert\psi_i\Vert. The optimum p⋆p^\star depends on the task solutions θk\theta_k, which are unknown in advance, whereas the norm rule is reward-independent and can be reused as tasks arrive.

Dependence on the distribution of bkb_k. The reward vectors enter part (a) only through SS. A single task gives a rank-one SS, and a reward-aware priority can do better. When the added tasks spread their solutions over more directions, SS can become closer to isotropic and the reward-free rule approaches the optimum. This is what happens on Four Rooms (300 seeds), where the excess factor of the sampling-dependent term falls from 4.64.6 at K=1K=1 to 1.11.1 at K=64K=64 (Appendix E.1).

When norm-based sampling overtakes PER. Propagating the residual to value error to first order gives a prediction of the ratio of norm-based to PER value error with no fitted constant:

KK1248163264
Predicted1.541.321.141.040.970.950.94
Measured, B=500B=5001.491.291.121.010.960.940.93
Measured, B=2000B=20001.511.301.121.020.970.940.93

The crossover between K=8K=8 and K=16K=16 in Figure 9 (left) is therefore predicted by the analysis, not only observed (table in Appendix E.1).

When b^k\hat b_k is also estimated (Proposition 3(b)). With b^k\hat b_k from the same mini-batch, the same variance analysis gives the minimizer pi∝∥ϕi∥⋅1K∑kδik2p_i\propto\Vert\phi_i\Vert\cdot\sqrt{\tfrac{1}{K}\sum_k\delta_{ik}^2}, where δik\delta_{ik} is the TD error of task kk at its solution, a feature-norm-weighted TD-error priority. In this regime the analysis explains why reward-aware priorities can be preferable, consistent with our observations in single-task and iterative TD (Figure 8, Appendix G). The two cases therefore explain why the appropriate sampling priority changes depending on whether the reward-dependent term is estimated from the same batch.

AuthorsOpenReview ↗

Response W2

W2. Applicability of Proposition 1 and Corollary 2

(i) Exact reward vector. We agree that Proposition 1 assumes an exact reward vector, and Appendix G shows that norm-based replay can perform worse in the single-task and iterative TD settings tested. Proposition 3(b) helps explain this limitation: when b^\hat b comes from the same batch, the optimal priority for the multi-task residual becomes a feature-norm-weighted TD-error priority.

(ii) Estimator used in the experiments. The main results hold with the exact unbiased estimator analyzed in the theory. On Four Rooms (B=500B=500, 300 seeds), norm-based sampling lowers value error relative to uniform replay by 14–16% for K≥8K\geq8, and the exact estimator is no worse than the self-normalized estimator used in the submitted figures in every configuration we tested (Appendix D.2). For MinAtar, applying the same importance-correction convention to norm-based replay and PER preserves the advantage over PER (20 of 32 configurations under either convention; Appendix J.3).

(iii) When the condition holds. On Four Rooms (300 seeds), the Frobenius condition ∥A^−A∥F<σλ\Vert\hat A-A\Vert_F<\sigma_\lambda holds in 60% of draws under norm sampling and 7% under uniform sampling at B=500B=500, and in all draws for both at B=2000B=2000. The stricter condition of Corollary 2 (≤σλ/2\le\sigma_\lambda/2) holds at B=2000B=2000 in 60% of draws under norm sampling against 7% under uniform sampling. Thus, norm sampling meets these sufficient conditions at smaller budgets than uniform sampling.

Sample complexity. We also derive a sufficient sampling budget (Corollary 4, Appendix E.2). With ui=∥ϕi∥∥ψi∥u_i=\Vert\phi_i\Vert\Vert\psi_i\Vert, the unbiased estimator has E∥A^−A∥F2=(uˉ2−∥A∥F2)/B\mathbb{E}\Vert\hat A-A\Vert_F^2=(\bar{u}^2-\Vert A\Vert_F^2)/B under norm sampling (with u2‾\overline{u^2} in place of uˉ2\bar{u}^2 under uniform sampling), giving, by Markov's inequality, the sufficient budget B≥(uˉ2−∥A∥F2)/(δσλ2)B\ge(\bar{u}^2-\Vert A\Vert_F^2)/(\delta\sigma_\lambda^2) for the condition to hold with probability at least 1−δ1-\delta. Since u2‾=uˉ2(1+CV2(u))\overline{u^2}=\bar{u}^2(1+\mathrm{CV}^2(u)), the corresponding uniform-sampling budget has a larger leading term, by a factor 1+CV2(u)1+\mathrm{CV}^2(u). This connects the required sampling budget to the priority-heterogeneity diagnostic used in the paper.

Proposition 1 also holds with the spectral norm in place of the Frobenius norm (the proof is unchanged), which gives a weaker condition. Importantly, these conditions are sufficient, not necessary for improvement. Repeating the experiment for λ\lambda from 0.10.1 to 10−310^{-3}, norm sampling keeps 0.800.80--0.850.85 times the value error of uniform sampling (K=16K=16, $B\in\lbrace 500,2000\rbrace $, unbiased estimator), including for λ≤0.003\lambda\le0.003, where the condition holds in none of the draws for either sampler (Appendix D.4). We have added this analysis to the revised paper (Appendix E.2).

We appreciate the time you have spent on this review, and we understand that the discussion period is limited. We hope Proposition 3 and Corollary 4 provide the sampler-specific analysis you asked for. If they address your concerns, we would be grateful if you would consider revising your score, and we would welcome any further questions.

References

  • Drineas, P., Kannan, R., and Mahoney, M. W. Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. SIAM Journal on Computing, 36(1):132–157, 2006.
Reviewer_dGxnOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a reward-agnostic data reuse strategy for linear TD policy evaluation with a replay buffer. The authors derive a reward-independent, norm-based sampling rule that prioritizes transitions and allows replay priorities to be reused across multiple reward functions without reward-specific re-computation. Experimental results demonstrate its effectiveness in multi-reward policy evaluation tasks.

Critical strengths
  • The proposed sampling rule is supported by a clear mathematical formulation, providing a principled alternative to conventional reward-dependent replay methods (e.g., PER).

  • The reward-independent priorities can be reused across multiple reward functions, including those associated with unseen or newly introduced tasks. The experiments demonstrate the benefits of this approach in multi-reward policy evaluation.

Critical weaknesses
  • The reported improvements seem to largely rely on estimating the shared TD matrix AA while computing the reward-dependent vectors bb from the full buffer. This raises concerns about the method's practical applicability, as norm-based replay performs worse than uniform replay in iterative TD learning, where both AA and bb are estimated from sampled transitions.
Questions for authors
  • The paper reports that norm-based replay performs worse than uniform replay in iterative TD learning. Could the authors clarify which practical RL settings would benefit most from the proposed approach, particularly when both the shared matrix and reward-dependent vectors must be estimated from mini batches?

  • Given that the theoretical results assume fixed linear features and a fixed policy, how should the gains observed in DQN be interpreted when both the learned representation and policy change during training?

2 comments

We thank the reviewer for the positive assessment, and in particular for recognizing that reward-independent priorities can be reused across multiple reward functions, including unseen or newly introduced tasks. This reuse is the central idea of the paper, and both questions concern its scope and practical applicability.

Q1. Which practical settings benefit when both AA and bb must be estimated from mini-batches?

Our main setting is multi-task prediction, where an estimate of the shared matrix AA can be reused across many reward functions. The method is not intended as a general replacement for uniform or reward-aware sampling in single-task iterative TD.

Role of the full-buffer bkb_k. In the closed-form experiments, bkb_k is computed from the full buffer to remove the reward-side error, so that the effect of the sampler on the shared matrix AA is measured independently. In this setting, norm-based replay improves over uniform replay for multiple tasks, including with the exact unbiased estimator (14–16% lower value error for K≥8K\geq 8, Appendix D.2).

Why iterative TD behaves differently. When each update also estimates b^k\hat b_k from the batch, the reward-agnostic importance weights can increase reward-side estimation error, offsetting the benefit of a better matrix estimate. Figure 8 (Appendix G) separates the two effects, and a new closed-form experiment supports this explanation: drawing b^k\hat b_k from a separate uniform batch removes the observed penalty (Appendix G.1).

Settings that benefit most.

  1. Many predictions over shared features and dynamics, such as Horde-style collections of GVFs (Sutton et al., 2011) and successor features (Dayan, 1993; Barreto et al., 2017), where one estimate of AA serves all tasks.
  2. Tasks that arrive after the replay distribution is fixed. Norm priorities need no reward information: they transfer to 50 unseen GVFs better than PER priorities built from one task (Figure 1), and under task arrival they reach lower error than PER at larger task counts, even when PER recomputes its priorities every round.
  3. Auxiliary predictions in deep RL. The MinAtar auxiliary heads are trained by iterative TD on shared mini-batches, and norm-based replay lowers their held-out GVF Bellman residual relative to PER in 31 of 32 configurations (Appendix J.4).

For a single reward estimated from each mini-batch, reward-aware sampling such as PER can be better aligned with the objective, as Section 4 states.

Q2. How should the DQN gains be interpreted when features and policy change?

What the theory covers. The sampling result does not require a fixed policy. For any fixed set of transitions and features, sampling in proportion to ∥ϕi∥∥ψi∥\Vert\phi_i\Vert\Vert\psi_i\Vert minimizes the expected squared Frobenius error of the unbiased estimate of the matrix they define (Section 3). In DQN, the auxiliary heads are linear in the penultimate features, so for a fixed snapshot of the learned features and policy, they share a TD matrix (for the action-conditional heads, the norm-ϕ\phi score approximates the optimal sampler for that matrix). The priorities are computed from the target network's features and refreshed every 10410^4 environment steps from the latest target network, so the priorities are updated as the representation changes. The fixed-policy assumption determines the policy-evaluation interpretation of the matrix, not the optimality of the sampler for estimating it.

What the experiments test. We do not claim convergence guarantees for jointly changing features and policies. The DQN experiments test whether the principle carries over:

  1. Auxiliary prediction. On a common held-out set, the GVF Bellman residual is lower than PER's in 31 of 32 configurations and lower than uniform replay's in 22 (Appendix J.4).
  2. Robustness. The return advantage over PER holds under matched importance correction (20 of 32) and without the periodic refresh (21 of 32 for a variant that scores transitions at insertion; Appendices J.3 and J.6).
  3. Consistency with the linear diagnostic. Gains grow with priority heterogeneity in the linear experiments; on MinAtar, Breakout has the least heterogeneous scores (Gini 0.1060.106 at initialization) and is where the samplers perform similarly (Section 5).

We therefore read the DQN results as empirical evidence that the shared-matrix view remains useful with learned features, rather than as a direct consequence of the linear theory.

Thank you again for your time and for your positive assessment. We hope these responses clarify where the method applies. If they do, we would appreciate your continued support, and we are glad to address any further questions during the discussion.

AuthorsOpenReview ↗

References

  • Barreto, A., Dabney, W., Munos, R., Hunt, J. J., Schaul, T., van Hasselt, H., and Silver, D. Successor features for transfer in reinforcement learning. In Advances in Neural Information Processing Systems, 2017.
  • Dayan, P. Improving generalization for temporal difference learning: The successor representation. Neural Computation, 5(4):613–624, 1993.
  • Sutton, R. S., Modayil, J., Delp, M., Degris, T., Pilarski, P. M., White, A., and Precup, D. Horde: A scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems, pp. 761–768, 2011.
Reviewer_W9WDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work proposes a reward-independent sampling priority for the shared matrix in linear TD/LSTD: the current-feature norm multiplied by the discounted feature-difference norm. With inverse-probability correction, it is the classical approximate-matrix-multiplication sampler that minimizes expected squared Frobenius error within the stated family of unbiased estimators. A standard perturbation bound connects sufficiently small matrix error to regularized LSTD parameter error for a fixed reward vector. Chain and Four Rooms experiments test matrix estimation, value prediction, and reuse across multiple or newly arriving cumulants. Related feature-norm priorities are then tested with DQN on four MinAtar games, where return gains are mixed and auxiliary prediction diagnostics provide additional evidence.

Critical strengths

Viewing the tasks through their shared matrix gives a clear reason to try reward-agnostic sampling. The AMM result has a straightforward interpretation here, and the authors correctly restrict the optimality claim to the chosen estimator and loss. They do not equate it with optimal value prediction. Reusing priorities when new cumulants arrive is a useful application of the idea.

I also appreciate the attention to cases where the method fails. The A-versus-b decomposition and the comparison of closed-form solutions with iterative TD show that a better matrix estimate can still lead to worse learning. Along with the DQN importance-correction ablation, these results make the paper more informative than an aggregate performance comparison alone would have been.

The computational benefit is not justified to me because computing all the b vectors already requires going through the full buffer.

Critical weaknesses

I could not determine exactly which estimator produced the central replay-buffer results. Appendix D defines A-hat with per-batch max-normalized importance weights, whereas the guarantee applies to an unbiased estimator; the paper acknowledges the distinction. In the closed-form multi-reward experiments, b_k comes from the full buffer. Normalizing only the sampled A changes its scale relative to b_k and the fixed regularizer, including at beta=1. Alpha=1 is specified for the linear experiments, but the beta and normalization used in each replay-buffer figure are not unambiguous.

The practical advantage is also still uncertain. The strongest multi-reward results assume full-buffer reward vectors, while iterative TD performs worse than uniform sampling in Figure 9. The cost of obtaining those vectors and maintaining priorities is not compared with maintaining the full shared matrix or another sketch. The DQN results do not settle this: the main norm curves omit importance correction while PER uses it, several gains disappear when correction is added, and auxiliary residuals are evaluated on different learned replay distributions rather than a common independent set. My weak-reject recommendation comes from these unresolved estimator and cost/accuracy questions, rather than from the matrix-estimation motivation itself.

Other limitation: Regarding Four Rooms (Appendix F.4), you define value error using the regularized full-buffer LSTD solution as a reference. While it's nice to see that the sampled approach gets close to this reference, it is important to note that the reference itself could have prediction error. It would be nice to see how close the methods get to the true expected returns under the policy.

Questions for authors
  1. For Figures 1 and 6–9, what are alpha, beta, the importance-weight normalization, and the exact definitions of A-hat and b-hat? If b_k is computed from the full buffer, is the normalization of A reversed before solving? Please show whether the key transfer result holds with the exact unbiased AMM estimator.

  2. What does the full procedure cost, including building or refreshing priorities, obtaining all b_k, and solving the systems? A comparison with accumulating A from the full buffer or using a conventional sketch would help identify the feature dimensions and task-arrival regimes where sampling is preferable.

  3. How are singular sampled systems handled in the unregularized chain experiments? With tabular features, the sampled matrix's rank cannot exceed the number of distinct sampled states, so an inverse is unavailable at many small budgets. Please specify any pseudoinverse, regularization, or failed-solve handling.

  4. Can norm sampling and PER be compared with the same importance-correction convention in the main deep-control results? For auxiliary prediction, a common held-out transition set or rollout-based target would help separate prediction improvements from differences in the replay distribution.

4 comments
AuthorsOpenReview ↗

Response Q1

We thank the reviewer for the constructive review, and for recognizing the motivation from the shared matrix, the reuse of priorities for new cumulants, and our reporting of failure cases. We address the concerns about the estimator and the cost/accuracy trade-off below.

Q1. Exact estimator and normalization

Our description was ambiguous, and we have corrected it in the revision.

Estimator and normalization. In the closed-form experiments (Figs. 1, 6, 8, and 9-left), norm sampling uses pi∝∥ϕi∥∥ψi∥p_i \propto \Vert\phi_i\Vert\Vert\psi_i\Vert (α=1\alpha = 1), with full inverse-probability weights wj=1/(Npij)w_j = 1/(Np_{i_j}) (β=1\beta = 1); the PER variants use α=0.6\alpha=0.6 on the oracle TD errors with the same weights. The implemented estimator is self-normalized, A^=∑j=1Bwjϕijψij⊤/∑j=1Bwj\hat A = \sum_{j=1}^B w_j \phi_{i_j}\psi_{i_j}^{\top} \big/ \sum_{j=1}^B w_j. Here, A^\hat A estimates the empirical full-buffer TD matrix AB=1N∑i=1Nϕiψi⊤A_B = \frac{1}{N}\sum_{i=1}^N \phi_i\psi_i^\top, defined in Eq. (6) of the paper, using only BB sampled transitions from the buffer of size NN.

No max-normalization is applied in these experiments, so there is no normalization factor to reverse before solving. We acknowledge that self-normalization introduces finite-sample bias, unlike the exact unbiased AMM estimator analyzed theoretically. The max-normalized weights described in Appendix D are instead used in the iterative TD experiments (Figs. 7 and 9-right), with β\beta annealed from 0.4 to 1. These weights enter the stochastic TD updates rather than defining a separately constructed matrix estimate.

Definition of bkb_k and b^\hat b. In Fig. 1, bk=Φ⊤Dπrkb_k = \Phi^\top D_\pi r_k is the population quantity computed using the environment model, and we report the state-space RMSE of Φθk\Phi\theta_k against the population solution. In Fig. 9-left, bk=1N∑i=1Nϕick(si′)b_k = \frac{1}{N}\sum_{i=1}^N \phi_i c_k(s_i') is computed from the full replay buffer, and we report empirical occupancy-weighted RMSVE against the full-buffer solution. In both cases, we solve (A^+λI)θk=bk(\hat A + \lambda I)\theta_k = b_k with λ=0.01\lambda = 0.01.

Fig. 6 evaluates matrix-estimation accuracy using the relative Frobenius error ∥A^−AB∥F/∥AB∥F\Vert\hat A-A_B\Vert_F/\Vert A_B\Vert_F; no bkb_k is estimated. In the AA/bb decomposition (Fig. 8), wherever b^\hat b is sampled, it is estimated using the same self-normalized importance weights, b^=∑j=1Bwjϕijc(sij′)/∑j=1Bwj\hat b = \sum_{j=1}^B w_j\phi_{i_j}c(s_{i_j}') \big/ \sum_{j=1}^B w_j.

Exact unbiased AMM estimator. We re-ran the closed-form multi-task experiment of Fig. 9-left using the exact unbiased AMM estimator, A^AMM=1B∑j=1Bϕijψij⊤/(Npij)\hat A_{\mathrm{AMM}} = \frac{1}{B}\sum_{j=1}^B \phi_{i_j}\psi_{i_j}^{\top}/(Np_{i_j}), without self-normalization, over 300 seeds.

Norm sampling reduces value error by approximately 14–16% relative to uniform sampling at B=500B=500 for K≥8K \geq 8 (e.g., a paired difference of −0.0020±0.0002-0.0020 \pm 0.0002 at K=16K=16).

Furthermore, the unbiased estimator is no worse than the self-normalized estimator across all eight tested (B,K)(B,K) configurations ($B\in\lbrace 500,2000\rbrace $ and $K\in\lbrace 1,8,16,64\rbrace $). Thus, the improvement persists under the estimator covered by the theory (Appendix D.2).

Key transfer result (Fig. 1) with the exact estimator. We also re-ran the held-out transfer and task-arrival experiments of Fig. 1 with the exact unbiased estimator (same buffers, tasks, and sampling seeds, 300 seeds). Re-running the submitted self-normalized version reproduces the published values, and the result holds with the exact estimator. At B=500B=500, the transfer error on the 50 unseen tasks is:

Training tasksUniformNorm (unbiased)PER-train (unbiased)
10.01320.01160.0243
40.01300.01170.0159
160.01330.01170.0131
640.01330.01180.0129

Norm sampling has the lowest transfer error for every number of training tasks and every budget we tested ($B\in\lbrace 100,500,2000\rbrace $). Under task arrival at B=500B=500, it has lower error than PER with priorities recomputed every round from 16 active tasks onward.

Dependence on the regularizer. The improvement also persists for λ\lambda from 0.10.1 to 10−310^{-3} (Appendix D.4).

We have added these results, together with the precise estimator, normalization, and evaluation-metric definitions for each figure, to Appendix D (D.1–D.4) of the revised paper.

AuthorsOpenReview ↗

Response Q2 and Q3

Q2. Computational advantage

Linear experiments. The primary goal of our controlled linear experiments is to understand whether norm-based sampling improves the estimate of the shared matrix AA under a limited sampling budget. To isolate this effect, we obtain bkb_k independently (either from the known environment model or the full replay buffer), and reuse the estimated shared matrix across tasks.

Cost accounting. For KK tasks, a replay buffer of NN transitions, and dd-dimensional features (assuming features are available):

StepFull-buffer LSTDNorm sampling
PrioritiesNot requiredO(Nd)O(Nd)
Shared matrix AAO(Nd2)O(Nd^2)O(Bd2)O(Bd^2)
All bkb_kO(KNd)O(KNd)O(KNd)O(KNd)
Factorization and solvesO(d3+Kd2)O(d^3+Kd^2)O(d3+Kd2)O(d^3+Kd^2)

Thus, norm sampling reduces the matrix-construction cost from O(Nd2)O(Nd^2) to O(Nd+Bd2)O(Nd+Bd^2), which is particularly useful when B≪NB\ll N and dd is sufficiently large. The benefit is therefore greatest when constructing the shared matrix is a substantial part of the total cost. With fixed features and policy, the priorities are reward-independent and can be reused across existing and newly arriving tasks without reward-specific recomputation, as illustrated in Fig. 1.

Comparison with conventional sketching. We additionally compared norm sampling against uniform sampling and CountSketch on Four Rooms (K=16K=16 tasks, unbiased estimator, 300 seeds), using m=Bm=B sketch rows. At B=500B=500, norm sampling achieves value error 0.0107, compared with 0.0129 for uniform and 0.0132 for CountSketch. The advantage over CountSketch persists across all tested approximation sizes (B=100B=100--20002000; Appendix I.2).

Deep RL. Our MinAtar experiments extend the same sampling principle to learned representations without explicitly constructing AA or bb. Norm-ϕ\phi refreshes its feature-based priorities every 10410^4 environment steps, which amortizes to N/T=10N/T=10 target-network forward passes per environment step for a buffer of N=105N=10^5 transitions, independent of the batch size (Appendix I.3).

Refresh-free variant. To test whether these gains depend on the periodic refresh, we additionally evaluated an online variant that scores each transition once at insertion and rescores only the sampled transitions after each update, as PER does with TD errors. Across four games and eight batch sizes, the online variant outperforms PER (α=0.6\alpha=0.6) in 21 of 32 configurations, although the refreshed version remains better overall. It maintains its priorities incrementally, as PER does (scoring at insertion and rescoring the sampled batch), so the advantage over PER does not require full-buffer refreshes. The variants differ in importance correction; Q4 provides the matched comparison. We have added these results to Appendix J.6. Because this variant maintains its priorities the same way PER does, we will move it into the main text (Section 5) in the final version.

We have added the cost table and the per-step cost of the DQN samplers to Appendices I.1 and I.3.

Q3. Singular systems in the random-chain experiments

The numerical treatment of singular systems was not made sufficiently clear in the paper, and we have clarified it.

Matrix error. Our primary matrix-estimation results measure ∥A^−A∥F\Vert\hat A-A\Vert_F, which does not require matrix inversion and remains well-defined even when A^\hat A is rank-deficient.

Value error. For the tabular and random-feature experiments, we use the Moore–Penrose pseudoinverse, θ^=A^+b\hat\theta=\hat A^+b, which provides a minimum-norm least-squares solution even when A^\hat A is singular. For the shared representation, we solve (A^+10−12I)θ^=b(\hat A+10^{-12}I)\hat\theta=b, where the small diagonal term is included for numerical stability.

As the reviewer correctly notes, the sampled tabular matrix can be rank-deficient at small budgets. The pseudoinverse allows us to evaluate these cases rather than discard them, with limited state coverage contributing to the plateau in the low-budget value-error curves. All sampled systems were evaluated; no draws were discarded due to rank deficiency.

We have documented the solvers and the rank-deficiency handling in Appendix F.4 of the revised paper.

AuthorsOpenReview ↗

Response Q4

Q4. Fairness of the DQN comparisons and importance sampling

The original experiments used different importance-correction conventions and evaluated auxiliary predictions on each run's own buffer. We have added controlled comparisons addressing both concerns. Our main interest is whether reward-independent priorities improve auxiliary predictions that share the same dynamics and learned features, while remaining competitive on the control task.

Auxiliary prediction. Following the reviewer's suggestion, we evaluated the GVF predictions on a common held-out transition set (10,000 transitions per game) collected by a separate agent and shared across all runs of each game. All samplers predict the discounted returns of the same 32 cumulants (a fixed random projection of the observation that is never trained) with the same discount. With norm-ϕ\phi under the same annealed correction schedule as PER, norm-ϕ\phi achieves lower Bellman residuals than PER in 31 of 32 configurations, and than uniform replay in 22 of 32 configurations. The improvement therefore persists under a common evaluation distribution. The residual is measured against each run's own target network, averaged over training, rather than against rollout-based returns, so it measures Bellman residual rather than true value error.

Return under matched importance correction. In our original experiments, we followed the standard convention of annealed importance correction for PER, while norm-based replay was evaluated without correction; Appendix J.2 already includes an ablation with fully corrected norm sampling.

To address this concern more directly, we additionally compared both samplers using the same priority exponent (α=0.6\alpha=0.6) and importance-correction conventions, isolating more directly the effect of the prioritization signal (∥ϕ∥∥ψ∥\Vert\phi\Vert\Vert\psi\Vert versus ∣δ∣|\delta|). We evaluated all four MinAtar games across eight batch sizes (32 configurations, 30 seeds each, with learning rates selected by return AUC separately for each method and configuration). Wins and losses denote differences in return AUC exceeding two standard errors; the remaining configurations are within two standard errors.

Importance correctionNorm vs. PER (W/T/L)Norm vs. uniform (W/T/L)
Both corrected (β:0.4→1\beta: 0.4\rightarrow1, max-normalized)20 / 6 / 613 / 9 / 10
Both uncorrected (β=0\beta=0)20 / 5 / 713 / 14 / 5

Norm-based replay outperforms PER in the majority of configurations under both conventions, indicating that the observed advantage is not explained by the difference in importance correction. Against uniform replay it has more wins than losses under both conventions, so returns remain competitive. Q2 shows that the advantage over PER also persists without the periodic refresh.

Learning rates selected on separate seeds. Because the learning rate is selected and reported on the same 30 seeds, we also selected each method's learning rate on seeds 0–14 and evaluated on seeds 15–29, and the reverse. Only 9 and 6 of the 96 learning-rate choices behind the held-out evaluation change. Restricting to configurations with unchanged learning rates, norm-ϕ\phi keeps a lower held-out GVF residual than PER in 25 of 26 and 27 of 29 configurations, showing that the held-out advantage persists in these configurations when tuning and evaluation seeds are separated. The additional return comparisons show a similar pattern (Appendix J.5).

We have added these controlled comparisons and held-out evaluation results to Appendices J.3–J.5 of the revised paper.

AuthorsOpenReview ↗

Response Q5

Q5. Norm-based replay performs worse than uniform replay in iterative TD

We view the iterative-TD result as marking the boundary of our claim rather than contradicting it, and we re-examined it to better understand why it occurs.

Source of the gap. Norm-based priorities target the error in the shared matrix A^\hat A. In iterative TD, every mini-batch also estimates the reward-dependent term b^k=1B∑jwjϕjck(sj′)\hat b_k=\frac{1}{B}\sum_j w_j \phi_j c_k(s_j'). Because the norm priorities do not depend on the cumulants, sampling can increase the error in b^k\hat b_k, offsetting the benefit of a better matrix estimate. The decomposition in Figure 8 (Appendix G) separates the two sides: when only A^\hat A is sampled, norm-based replay lowers the value error relative to uniform replay, whereas when b^\hat b is also estimated from the batch, the reward channel dominates. In an additional closed-form experiment with the exact unbiased estimator (Four Rooms, K=16K=16, B=500B=500, 300 seeds), estimating A^\hat A and b^k\hat b_k from the same norm-sampled batch gives a higher error than uniform sampling (0.0530.053 versus 0.0370.037), while drawing b^k\hat b_k from a separate uniform batch of the same size (2B2B transitions in total, as for two uniform batches) removes the penalty (0.0356±0.00040.0356\pm0.0004 versus 0.0374±0.00050.0374\pm0.0005 for two uniform batches). This supports our explanation that the penalty is associated with estimating the reward-dependent term from the same norm-sampled batch, rather than from the matrix estimate alone. Proposition 3(b) (Appendix E.1) provides further insight: when b^k\hat b_k is sampled from the same batch, the optimal priority becomes a feature-norm-weighted TD-error priority. We have added this experiment to Appendix G.1 of the revised paper.

Contribution of the step size. In the submitted iterative TD runs, the max-normalized importance weights also shrink the effective step size: the mean weight under norm sampling is 0.120.12 at K=16K=16. A uniform sampler whose step size is scaled by the same factor achieves comparable value error (0.0790.079 versus 0.0770.077), suggesting that step-size reduction contributes to the gap in Figure 9. With each sampler's step size tuned separately and unbiased weights, norm-based replay remains worse than uniform replay (2.4×2.4\times at K=16K=16), consistent with the reward-side explanation above. Section 4 of the revised paper states this limitation: a better A^\hat A does not by itself resolve the error in per-step TD, where the reward-dependent part of the update is also estimated from each mini-batch.

Settings that benefit. The approach is intended for settings in which the shared matrix is the expensive and reusable part of the problem:

  1. Many predictions sharing features and dynamics. One estimate of AA (or its factorization) is reused across all KK tasks.
  2. Tasks that arrive after the replay distribution is built. Norm priorities are computed before the cumulants are known, so new GVFs can be added without recomputing reward-dependent priorities.
  3. Auxiliary predictions in deep RL. The MinAtar heads are trained by iterative TD on learned features, and there norm-based replay lowers the held-out GVF residual (Q4).

Points added in the updated review

Cost of the bb vectors. We agree that computing all bkb_k requires a pass over the buffer, so both procedures read every transition once. The saving is in the per-transition cost of that pass: full-buffer LSTD also updates AA at O(d2)O(d^2) per transition, while norm sampling builds A^\hat A from only BB transitions. Sampling therefore reduces the total cost when dd is comparable to or larger than KK. The main benefit, however, is accuracy: for a given budget, norm sampling gives a more accurate A^\hat A, which every task reuses, including tasks that arrive later.

Error against the true values. On Four Rooms, the full-buffer reference is itself far from the true values vπv_\pi, because the RBF features cannot represent them exactly, and measured against vπv_\pi all samplers give essentially the same error. The error to the true values is therefore set by the representation, which no sampler can change. We measure against the full-buffer solution because it isolates the estimation error that the sampler controls.

We appreciate the time you have put into this review, and we understand that the discussion period is short. We hope the new results resolve your concerns about the estimator, the cost, and the fairness of the DQN comparisons. If they do, we would be grateful if you would consider revising your score, and we are happy to answer any remaining questions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Common response to all reviewers

We thank the reviewers for their careful reading and constructive feedback. All three reviews recognize that the reward-independent priorities can be reused across tasks, including tasks that arrive later. We also appreciate the positive comments on the paper's formulation and its analysis of when the method helps and when it does not. The main questions concerned which estimator produced the results, what the method costs, whether the theory covers the regimes we test, and how to read the DQN results. Addressing these concerns has helped us clarify the paper's claims and strengthen both its theoretical and experimental analysis. The revision adds the following (new text in blue; removed text struck through):

  1. Exact unbiased estimator (W9WD, LXzF). The closed-form multi-task result holds with the exact unbiased AMM estimator: 14–16% lower value error than uniform sampling for K≥8K\geq8 (Appendix D.2).
  2. A sampler-specific multi-task result (LXzF). Proposition 3 gives the exact expected multi-task residual under any sampler. It characterizes when norm sampling is optimal, predicts the observed crossover with PER, and explains why the optimal priority changes when b^k\hat b_k is estimated from the same batch (Appendix E.1). Corollary 4 gives a sufficient budget for the condition of Proposition 1, and we report how often the condition holds (Appendix E.2).
  3. Cost and sketching (W9WD). We add a cost table, the per-step cost of the DQN samplers, and a comparison with CountSketch, against which norm-based sampling has lower value error at every budget we tested (Appendix I.2).
  4. Deep RL (W9WD, dGxn). On a common held-out transition set, norm-based replay lowers the GVF residual relative to PER in 31 of 32 configurations. Under matched importance correction its return is higher than PER's in 20 of 32, and a variant without the periodic refresh also retains an advantage over PER (Appendices J.3-J.6). In the final version we will move this refresh-free variant into the main text.
  5. Iterative TD (all reviewers). A split-batch experiment helps explain the iterative TD limitation: estimating b^k\hat b_k from a separate uniform batch removes the penalty observed in the closed-form experiment (Appendix G.1), and Proposition 3(b) explains why (Appendix E.1).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.