- 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 that depends on the policy, transition dynamics, and feature representation, and a reward dependent vector that depends on the reward or cumulant. When multiple predictions share the same policy and features, is shared across tasks while each task has its own vector . By expressing and its replay buffer analogue as a product of two feature matrices, the authors formulate estimating under a limited budget as an approximate matrix multiplication (AMM) problem. This yields a norm based sampling rule that prioritizes each transition by the product of the norms of the current state feature and the discounted one step feature difference . Within the unbiased AMM estimator family, this rule minimizes the expected squared Frobenius error of the estimate . 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 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 from the reward vector in LSTD, the proposed norm based priority depends only on the feature vectors and , 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 to explain when targeted sampling improves over uniform replay, and they include informative ablations on and that clearly show why reward aware PER remains superior in single task and iterative TD settings where estimation error in 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 (or its empirical replay buffer analogue ) 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 (lines 203 to 204), so it does not apply to single task prediction from a sampled batch or iterative TD updates where 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 , importance sampling exponent , and max normalization, or omit importance sampling correction entirely by setting 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 and to be smaller than , the smallest singular value of , 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 GVF tasks when both and are estimated, that explains when norm based sampling overtakes reward dependent PER as grows and how this depends on the distribution of reward vectors ?
2 comments
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 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 (, 300 seeds), norm-based sampling lowers value error relative to uniform replay by 14–16% for , 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 holds in 60% of draws under norm sampling and 7% under uniform sampling at , and in all draws for both at . The stricter condition of Corollary 2 () holds at 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 , the unbiased estimator has under norm sampling (with in place of under uniform sampling), giving, by Markov's inequality, the sufficient budget for the condition to hold with probability at least . Since , the corresponding uniform-sampling budget has a larger leading term, by a factor . 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 from to , norm sampling keeps -- times the value error of uniform sampling (, $B\in\lbrace 500,2000\rbrace $, unbiased estimator), including for , 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.
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 A, 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 bk 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 and A^=B1∑jϕijψij⊤/(Npij). Then θ^k−θk=−(A^+λI)−1(A^−A)θk exactly, so the residual (A^−A)θk is the quantity the sampler controls.
Proposition 3(a) (exact bk). For any sampling distribution p, K1∑kE∥(A^−A)θk∥2=B1[N21∑ipi∥ϕi∥2ψi⊤Sψi−K1∑k∥Aθk∥2],S=K1∑kθkθk⊤. It is minimized by pi⋆∝∥ϕi∥ψi⊤Sψi. The norm rule pi∝∥ϕi∥∥ψi∥ is exactly optimal when S∝I; in general, its sampler-dependent term exceeds the optimum by the factor 1+CV2(r), where ri=ψi⊤Sψi/∥ψi∥ and the coefficient of variation is taken under weights ∥ϕi∥∥ψi∥. The optimum p⋆ depends on the task solutions θ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 bk. The reward vectors enter part (a) only through S. A single task gives a rank-one S, and a reward-aware priority can do better. When the added tasks spread their solutions over more directions, S 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.6 at K=1 to 1.1 at K=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:
The crossover between K=8 and K=16 in Figure 9 (left) is therefore predicted by the analysis, not only observed (table in Appendix E.1).
When b^k is also estimated (Proposition 3(b)). With b^k from the same mini-batch, the same variance analysis gives the minimizer pi∝∥ϕi∥⋅K1∑kδik2, where δik is the TD error of task k 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.