acceptodds
Withdrawn from ICLR 2027

R-GTD: A Geometric Analysis of Gradient Temporal-Difference Learning in Singular Regimes

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

Abstract

Gradient temporal-difference (GTD) learning provides a principled approach to off-policy policy evaluation with linear function approximation. However, existing convergence analyses rely on the restrictive assumption that the so-called feature interaction matrix (FIM) is nonsingular. In practice, the FIM can become singular and leads to instability or degraded performance. In this paper, we propose a regularized optimization objective by reformulating the mean-square projected Bellman error minimization. This formulation naturally yields a regularized GTD algorithms, referred to as R-GTD, which guarantees convergence to a unique solution even when the FIM is singular. We conduct a geometric analysis to establish theoretical convergence guarantees and explicit error bounds for the proposed method, and validate its effectiveness through empirical experiments.

Primary area:
reinforcement learning
Keywords:
Gradient temporal-difference learning, Off-policy policy evaluation, Linear function approximation, Regularization

Reviews

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

R-GTD regularizes projected Bellman-error minimization to obtain a unique solution even when the feature interaction matrix is singular. Its geometric analysis characterizes the selected minimum-value-norm solution, helping distinguish stable convergence from the ambiguity of unregularized policy evaluation.

Critical strengths
  1. The paper addresses singular feature interaction matrices directly, rather than assuming invertibility.
  2. The limiting solution is characterized geometrically, clarifying which component of the GTD2 solution set regularization selects.
Critical weaknesses
  1. Unique solution selection does not establish better prediction. Theorem 4.4 retains a term measuring mismatch with the true projected value. Removing the null-space component therefore need not improve value accuracy, particularly beyond the deliberately large null-space initializations used in several experiments.
  2. The Baird experiment does not match the stated feature assumption. Figure 6 shows seven states with eight parameters, so the feature matrix cannot have full column rank. The paper should explain any feature reduction and how the reference parameter is chosen, especially since it reports parameter error rather than value error.
Questions for authors

See weaknesses.

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

This paper studies gradient temporal-difference learning when the projected Bellman operator is singular or nearly singular. It introduces R-GTD through a constrained, regularized optimization problem and derives a three-variable stochastic algorithm. The theoretical results establish asymptotic convergence for a fixed regularization parameter and characterize the limiting solution as regularization vanishes. In particular, the regularization path selects the minimum-BB-norm element of the unregularized solution set.

Critical strengths
  • The paper addresses a limitation of analyses that assume a nonsingular projected Bellman operator.
  • The characterization of the regularization path and its minimum-BB-norm limit is informative.
  • The experiments cover several environments, include regularized baselines, and investigate sensitivity to the regularization parameter.
Critical weaknesses
  1. Comparison to GTD4 from Lee et al., New Versions of Gradient Temporal-Difference Learning is missing.
    Using the manuscript's notation, let r(θ)=Mθ+br(\theta)=M\theta+b. Eliminating the auxiliary variable from the R-GTD optimization problem gives
    JR(θ)=c2r(θ)⊤B−1r(θ)+12θ⊤Bθ.J_{\mathrm{R}}(\theta)=\frac{c}{2}r(\theta)^\top B^{-1}r(\theta)+\frac{1}{2}\theta^\top B\theta.
    Maximizing over the dual variable in the stated GTD4 saddle objective gives
    J4(θ)=12r(θ)⊤B−1r(θ)+σ2θ⊤Bθ.J_4(\theta)=\frac{1}{2}r(\theta)^\top B^{-1}r(\theta)+\frac{\sigma}{2}\theta^\top B\theta.
    Thus, with σ=1/c\sigma=1/c,
    JR(θ)=cJ4(θ).J_{\mathrm{R}}(\theta)=cJ_4(\theta).
    This equivalence with GTD4 substantially limits the novelty of the paper. The regularized objective, its optimizer, and the minimum-B-norm solution selected as regularization vanishes are shared with GTD4. The remaining contributions appear to be an alternative three-variable recursion and a geometric analysis of this existing regularization path. Moreover, GTD4's mean dynamics are already stable for singular M when B is positive definite and the regularization parameter is positive, as follows directly from its Lyapunov argument. The paper therefore needs to establish what the additional auxiliary variable achieves and explain why the geometric analysis constitutes a substantial advance.
  1. The proof of Theorem 4.1 largely applies existing machinery. The regularized objective is strongly convex, and the augmented constraint matrix [M;B][M\\;B] has full row rank because B≻0B\succ0, even when MM is singular. This allows the authors to invoke the primal-dual gradient dynamics result of Qu and Li (2018), followed by the stochastic-approximation ODE method of Borkar and Meyn (2000). The convergence theorem therefore appears to be a relatively direct application of established results to the proposed formulation.

    More broadly, saddle-point formulations of GTD already appear in Macua et al. (2014), and regularized corrections for GTD were studied by Ghiassian et al. (2020). Together with the exact objective equivalence to GTD4, this places much of the burden of theoretical novelty on Lemma 4.3 and Theorem 4.4. However, Lemma 4.3 characterizes the limiting behavior of an existing regularization path, while Theorem 4.4 does not establish an improvement in approximation accuracy. I am therefore not convinced that the analysis provides a sufficiently substantial advance beyond the existing formulation and convergence tools.

  2. R-GTD maintains three coupled iterates, θ\theta, ww, and λ\lambda, updated on a common timescale. Related algorithms with an additional auxiliary state have been analyzed in Deb and Bhatnagar, Gradient Temporal Difference with Momentum: Stability and Convergence, which studies both single-timescale and three-timescale formulations. Deb et al., Multi Timescale Stochastic Approximation: Stability and Convergence develops a broader stochastic-approximation framework and applies it to momentum-based GTD methods. The paper should discuss these connections and distinguish the role of its auxiliary variable and its stability conditions from those in prior modified GTD algorithms.

  3. The introduction's statement that Yu (2017) restricts the optimal solution to the origin is inaccurate. Assumption 5.5(c), on page 79, concerns a scaled limiting objective in which the reward term has vanished. It does not require the original regularized policy-evaluation objective to have its minimizer at zero. Indeed, a positive-definite quadratic regularizer satisfies this origin condition even when MM is singular, while the original optimizer can be nonzero. Theorem 5.5 establishes convergence to the original optimizer set under its stated assumptions. The introduction should be corrected, and Appendix K should clarify what the origin condition actually requires.

  4. Theorem 4.4 contains a projection-difference term that is not quantitatively controlled. It compares the regularized solution with the unregularized minimizer set, but does not establish an improvement over the particular solution reached by GTD2. Uniqueness and stability of the regularized solution do not by themselves imply lower prediction error.
    The construction in Appendix M illustrates this limitation. A direct calculation gives the best approximation parameter

    θπ∗=(803,923)⊤,\theta_\pi^*=\left(\frac{80}{3},\frac{92}{3}\right)^\top,

    which belongs to the unregularized MSPBE minimizer set, whereas the regularization path converges to
    θ∞=(−2,2)⊤.\theta_\infty=(-2,2)^\top.

    Thus, selecting the minimum-BB-norm solution can leave a substantial prediction error even when the best approximation lies in the unregularized minimizer set. The statement that regularization “does not degrade performance” in the nonsingular case is also too strong. An O(1/c)O(1/c) perturbation establishes asymptotic closeness as cc grows, but does not establish non-degradation at a finite cc.

  5. Although the primary contributions of the paper are theoretical, some comments about the experiments: they emphasize large initial errors aligned with null or poorly conditioned directions. These settings demonstrate behavior under selected difficult initializations, but do not establish how broadly the advantage persists under ordinary initialization. The evaluation would be better if:

    • A GTD4 comparison using matched regularization, since it shares the same optimization target.
    • Learning curves showing prediction error against sample count and computational cost.
    • Results under ordinary random initialization alongside the deliberately difficult initializations.
    • Clear descriptions of baseline implementations and tuning budgets.
Questions for authors

See Weaknesses

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

The paper studies off-policy policy evaluation with linear function approximation in settings where the feature interaction matrix is singular or severely ill-conditioned, while assuming that the feature Gram matrix remains positive definite. The authors propose R-GTD, a three-variable stochastic primal-dual algorithm derived from a slack-variable formulation of the regularized mean-squared projected Bellman error (MSPBE).

The theoretical results establish almost-sure convergence under an i.i.d. sampling assumption and characterize the solution selected as regularization vanishes: among all minimizers of the unregularized MSPBE, R-GTD approaches the one with the smallest feature-weighted norm. The paper also presents a geometric decomposition of the approximation error relative to the true projected value.

Experiments compare R-GTD with GTD2 and regularized baselines on synthetic MDPs, Baird's example, and Frozen Lake, including sensitivity studies on initialization and matrix conditioning.

Critical strengths

1. A concrete treatment of singular regimes in off-policy policy evaluation.

The paper explicitly addresses settings where the feature interaction matrix is singular or nearly singular, while the feature Gram matrix remains positive definite. It develops a three-variable stochastic primal-dual algorithm with a uniquely defined regularized solution and establishes almost-sure convergence under the stated sampling assumptions. The slack-variable formulation provides a concrete way to implement regularization in this setting.

2. An interpretable characterization of solution selection.

The paper clearly identifies which solution is selected as regularization vanishes: the minimizer of the unregularized MSPBE with the smallest feature-weighted norm. This characterization helps explain the algorithm's behavior when multiple MSPBE minimizers exist. The initialization and condition-number experiments also provide useful illustrations of how regularization suppresses components along null or nearly singular directions. Although the novelty relative to standard Tikhonov regularization needs clarification, the geometric interpretation is informative.

Critical weaknesses

1. The theoretical novelty is not adequately distinguished from prior work on regularized GTD and standard Tikhonov regularization.

The paper's regularized MSPBE objective appears to be covered by the general differentiable convex regularization framework of Yu (2017). In particular, the positive-definite, feature-weighted quadratic penalty used by R-GTD satisfies the relevant condition in Yu's Assumption 5.5(c), even when the feature interaction matrix is singular.

Importantly, that assumption requires the origin to be the unique minimizer of a reward-free, rescaled limiting objective. It does not require the minimizer of the original, reward-dependent regularized MSPBE to be the origin. The manuscript's discussion of this restriction therefore appears to mischaracterize the prior result.

I recognize that R-GTD is not the same stochastic algorithm as Yu's method: it introduces an additional slack variable and uses sample-based estimates in its updates. However, the two formulations can target the same regularized solution. The paper needs to explain what additional theoretical guarantee follows from the three-variable formulation, rather than from the already-studied regularized objective.

The geometric characterization also appears closely related to standard Tikhonov regularization. After an appropriate change of coordinates using the positive-definite feature Gram matrix, the optimization problem reduces to ordinary ridge-regularized least squares. The uniqueness of the regularized solution, convergence to the minimum-norm unregularized solution, and the reported asymptotic rate then follow from standard linear-algebra arguments. A GTD-specific interpretation is useful, but the manuscript does not clearly establish what is technically new beyond this classical result.

Reference: Huizhen Yu, "On Convergence of some Gradient-based Temporal-Differences Algorithms for Off-Policy Learning," arXiv:1712.09652, Section 5.3, Assumption 5.5, and Theorem 5.5.

2. The practical value of the selected solution and the additional algorithmic variable is not sufficiently established.

Selecting the minimum-norm MSPBE minimizer does not necessarily produce the best approximation to the true value function. Theorem 4.4 decomposes the approximation error but leaves a solution-selection term uncontrolled. Consequently, the bound does not establish that this term becomes small as regularization vanishes.

The paper's own example in Appendix M illustrates the issue. The limiting R-GTD parameter is (-2, 2), whereas the parameter corresponding to the true projected value is (80/3, 92/3). Both belong to the unregularized MSPBE solution set, yet they represent substantially different approximate values. This does not contradict the theorem, but it shows that minimum-norm selection alone is not an accuracy guarantee.

The experimental evidence also does not isolate the benefit of the proposed three-variable dynamics. The largest improvements occur in stress tests with deliberately large initialization components along null or nearly singular directions. These tests illustrate the shrinkage mechanism, but provide limited evidence of an advantage under more typical initializations or when shrinkage removes useful value components.

Performance on the other benchmarks is mixed. R-GTD and the Yu baseline achieve very similar mean errors on Baird's example, while the Yu baseline achieves a lower mean error on Frozen Lake. More importantly, the implementation of the "Yu (2017)" baseline is not described precisely enough to determine its exact update, regularizer, regularization strength, or tuning procedure.

A particularly important missing comparison is a standard two-variable GTD algorithm using the same feature-weighted regularization penalty as R-GTD. Without this matched-objective comparison, it is difficult to tell whether any improvement comes from the choice of regularizer or from the new three-variable update.

Finally, the experiments emphasize final parameter error. Value-space error, MSPBE, convergence behavior, and distance to each algorithm's own regularized solution would help separate optimization performance from regularization bias.

Overall, the main concern is not that the proposed algorithm is necessarily incorrect, but that its theoretical and practical contributions are not yet convincingly separated from existing regularization techniques.

Questions for authors
  1. Relation to Yu (2017). Which specific assumption in Yu (2017), Section 5.3, excludes the positive-definite, feature-weighted quadratic regularizer used in this paper? My reading is that Assumption 5.5(c) concerns a reward-free limiting objective, rather than the optimizer of the original regularized MSPBE. If the proposed objective is already covered, what additional theoretical guarantee does the present analysis establish?

  2. Matched-objective baseline. What exact update equations and regularizer were implemented for the "Yu (2017)" baseline? How were the regularization coefficients and step sizes selected? In particular, does any baseline use exactly the same feature-weighted quadratic penalty as R-GTD? A comparison against a two-variable GTD method with the same objective would help isolate the benefit of the additional slack variable.

  3. Interpretation of the approximation guarantee. Theorem 4.4 leaves a solution-selection term uncontrolled, and the Appendix M example shows that the minimum-norm MSPBE solution can differ substantially from the true projected-value solution. Is minimum-norm selection intended only as a principled way to choose one MSPBE minimizer, or can the authors identify additional assumptions under which it also improves value-function accuracy?

  4. Sampling and feature-rank assumptions. The convergence proof in Appendix E explicitly uses i.i.d. samples. Were the experiments conducted using independent transition samples or single Markov trajectories? Also, the displayed Baird representation appears to use eight feature parameters for seven states. Was a modified feature representation used to satisfy the full-column-rank assumption? If not, how should the stated theoretical assumptions and the reported parameter errors be interpreted?

Answers to these questions would materially affect my assessment of the paper's novelty and empirical support.

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

Related papers

Discussion (0)

Sign in to comment.