acceptodds
Under review as a conference paper at ICLR 2027

Understanding the theoretical properties of projected Bellman equation, linear Q-learning, and approximate value iteration

Abstract

In this paper, we study the theoretical properties of the projected Bellman equation (PBE) and two algorithms to solve this equation: linear Q-learning and approximate value iteration (AVI). We identify two sufficient conditions for the existence of PBE solution: strictly negatively row dominating diagonal (SNRDD) assumption and a condition motivated by the convergence of AVI. The SNRDD condition further provides a unified view on the convergence of Q-learning algorithms: tabular, linear, and regularized Q-learning algorithms. We also examine its relationship with the convergence of AVI. Finally, we present examples under -greedy behavior policy showing the limitations of existing analyses of PBE solutions.

Primary area:
reinforcement learning
Keywords:
q-learning, projected bellman equation, approximate value iteration

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_1V6uOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper centres on the Projected Bellman Equation (PBE), a linear approximation of the Bellman equation, and employs linear Q-learning alongside approximate value iteration (AVI) as the machinery for learning it. The authors lay out a set of convexity assumptions that render this programme tractable. The SNRDD condition is then invoked to furnish a unifying lens on the convergence of Q-learning algorithms across three regimes — tabular, linear, and regularised. Existence guarantees are derived through fixed-point arguments, and the approach is compared against ε-greedy methods.

Critical strengths

The paper offers a rigorous, carefully constructed analysis of Markov decision processes, and it builds thoughtfully on the existing literature. The theoretical scaffolding is solid, and the unification offered by SNRDD is a genuinely useful principle.

Critical weaknesses

The central concern is whether SNRDD is an unreasonably strong assumption. Beyond the appeal that earlier authors have adopted a comparable setting, what independently motivates it? More plainly, the condition implies that a state's transition back to itself dominates its transitions to any other state — a structural constraint that considerably narrows the class of dynamical systems to which the results apply. This risks confining the paper's reach to a fairly narrow family of problems.

Questions for authors

How does the existence of many optimal solutions versus a single one bear on the results — does multiplicity weaken or reshape the guarantees?

How do these methods stack up empirically against modern deep RL baselines such as PPO or SAC?

In Fig. 2(a), the method does not appear to converge; it oscillates around the optimum. What does this oscillation reveal about the method's stability in practice?

3 comments

Q1. The central concern is whether SNRDD is an unreasonably strong assumption. Beyond the appeal that earlier authors have adopted a comparable setting, what independently motivates it? More plainly, the condition implies that a state's transition back to itself dominates its transitions to any other state—a structural constraint that considerably narrows the class of dynamical systems to which the results apply. This risks confining the paper's reach to a fairly narrow family of problems.

A1. We thank the reviewer for motivation on the regularization. We agree that SNRDD is a restrictive condition under function approximation. However, we would like to clarify that it is imposed on the parameter-space update matrix, not on the transition matrix itself. Consequently, it does not require a self-transition probability to dominate its transitions to other states. This discussion has been added to page 5 of the revised manuscript.

As the reviewer mentioned, the SNRDD condition can be difficult to met but regularization can be applied in practice in various forms. For example, one can adjust the regularization toward a reference parameter rather than necessarily toward zero. Specifically, we can consider min⁡θ∣∣yk−Φθ∣∣D2+∣∣Aθ−Aθˉ∣∣M2\min_{\theta} ||y_k - \Phi\theta ||^2_D + ||A\theta-A\bar{\theta} ||^2_M where θˉ\bar{\theta} can be zero or any other reference parameter, AA can be identity or feature matrix, and MM can some probability distribution. Using an exponential moving average of θk\theta_k as θˉ\bar{\theta} and MM to be a sampling distribution such that M(s,a)=d(s)⋅1∣A∣M(s,a)=d(s)\cdot\frac{1}{|A|}, which we call Reg-EMA-Q, we can see that regularization can help mitigate performance degradation and is robust to target network update period choice:

GameFinal-score drop (%): DQNFinal-score drop (%): Reg-EMA-QAUC drop (%): DQNAUC drop (%): Reg-EMA-Q
Boxing165.1±12.3165.1 \pm 12.3−1.8±11.5\mathbf{-1.8 \pm 11.5}154.7±4.4154.7 \pm 4.4−2.7±4.8\mathbf{-2.7 \pm 4.8}
Breakout48.3±6.5\mathbf{48.3 \pm 6.5}50.7±9.6\mathbf{50.7 \pm 9.6}32.4±3.6\mathbf{32.4 \pm 3.6}30.5±5.4\mathbf{30.5 \pm 5.4}
Kung Fu Master100.0±0.0100.0 \pm 0.015.4±29.3\mathbf{15.4 \pm 29.3}100.0±0.0100.0 \pm 0.018.6±9.2\mathbf{18.6 \pm 9.2}
Asterix27.6±11.127.6 \pm 11.1−10.9±11.3\mathbf{-10.9 \pm 11.3}39.4±5.839.4 \pm 5.84.8±3.0\mathbf{4.8 \pm 3.0}

Values are computed as 100(1−Gˉ1/Gˉ1000)100(1-\bar{G}_{1}/\bar{G}_{1000}), where Gˉi\bar{G}_i denotes the mean final evaluation score or mean area under the curve (AUC) at target update frequency ii. Lower is better and negative values indicate improvement. The details are presented in Appendix L of the revised paper.

Another motivation is that SNRDD expresses a contraction property of the learning dynamics that is already present in tabular Q-learning. Under linear function approximation, SNRDD provides an explicit sufficient condition under which the feature coordinates preserve contraction.

Q2. How does the existence of many optimal solutions versus a single one bear on the results. does multiplicity weaken or reshape the guarantees?

A2. We thank the reviewer for the comments on multiplicity of the solution versus single point solution. In general, there are no guarantee which is better. Nonetheless, the uniqueness can guarantee a convergence from any initialization point. In contrast, if the PBE admits multiple solutions, the global uniqueness and convergence guarantees no longer apply. One must instead examine the stability of individual solutions and their regions of attraction and convergence may depend on initialization. The disucssion has been added to page 4 of the revised manuscript.

Q3. Application of the methods to modern deep RL baselines such as PPO or SAC

A3. We thank the reviewer for the comments on the the implementation on PPO or SAC. The regularization can be applied to critics if we adopt an actor-critic design. Nonetheless, our targeted algorithms are specifically value-based methods rather than policy gradient approaches. Policy gradient approaches also suffer from function approximation and convergence is difficult to establish for policy gradient methods with function approximation. We have added this discussion in the conclusion part of the revised manuscript.

Q4. In Fig. 2(a), the method does not appear to converge; it oscillates around the optimum. What does this oscillation reveal about the method's stability in practice?

A4. We thank the reviewer for the clarification on oscillation. In practice, the oscillation in parameter space can imply that the policy is oscillating, which often causes noisy and unstable behavior of RL algorithms. This phenomenon is often called the policy churn [Schaul, 2022]. The examples show that even when solution exists, AVI can oscillate while Q-learning converges, and vice-versa. The discussion has been added to the Fig (2a) in the revised manuscript.

Schaul, Tom, et al. "The phenomenon of policy churn." NeurIPS (2022)

I have read the rebuttal, and appreciate the authors' efforts in addressing my concerns.

The main issue, as mentioned, is the generality of the the paper. The paper has its merits, in term of rigour and experimentation.

I've adjusted my score accordingly. I encourage the authors to incorporate the changes suggested by all reviewers into their article.

We thank the reviewer for the valuable comments to improve the manuscript. We have included the suggested changes and discussion with the reviewers in the newly updated revision and the changes are colored with blue fonts.

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

The main focus of this work is an analysis of the required conditions for the convergence of Q learning for the linear function approximation case. The chief main condition is on the Jacobian associated with the projected bellman equation which is required to have a strictly negatively row-dominating diagonal (SNRDD. That condition is then used to discuss the uniqueness of the PBE solutions and convergence of Q learning vs Approximate Value Iteration. The paper instantiates the results with a set of examples where either Q learning or AVI converge, in accordance with the theory. There is an additional structural explanation given about why multiple solutions and instability tend to converge together.

Critical strengths
  1. It gives a single unifying perspective on and the convergence of Q learning algorithms, connecting the convergence to the well-posedness of the projected bellman equation matrix.
  2. The work gives a more general analysis than prior works with fewer assumptions and in the off-policy settings with broad policy classes.
  3. It gives constructive examples which demonstrates which shows where Q learning and AVI converge while the other does not respectively.
Critical weaknesses
  1. The chief restriction here seems to be that the data comes from a fixed sampling distribution. In practice for Q learning, the data comes from the current iteration of the policy(plus a small exploration component in some cases), hence there is a mismatch between theory and practice.
Questions for authors
  1. The current analysis seems quite foundationally based in the tabular setting. What, if any, pathways do you see to extend this to a continuos and/or general function approximation setting?
  2. Can some standard policy concentrability assumptions extend the off-policy to the on-policy setting?
1 comment

Q1 The chief restriction here seems to be that the data comes from a fixed sampling distribution. In practice for Q learning, the data comes from the current iteration of the policy(plus a small exploration component in some cases), hence there is a mismatch between theory and practice.

A1. We thank the reviewer for the comments on time-varying behavior policy. We agree that fixed behavior policy is strict but it is a standard assumption in the theoretical literature on Q-learning [Melo and Ribeiro, 2007]. The Section 6 clearly shows the limitation of analysis when we use iterate dependent policy---ϵ\epsilon greedy policy---that contradicts the uniqueness and existence phenomenon happened in the fixed behavior policy case. We have added the disucssion on page 8.

Q2. The current analysis seems quite foundationally based in the tabular setting. What, if any, pathways do you see to extend this to a continuos and/or general function approximation setting?

A2. We thank the reviewer for the clarification on the extension to continuous state spaces and general function approximation setting.

For continuous state spaces with finitely many actions and a finite-dimensional linear approximator, a natural approach is to replace the finite-state matrix expressions with expectations under the sampling distribution. This would require suitable boundedness, integrability, and coverage assumptions, together with an analogous uniform SNRDD condition on the resulting parameter-space.

For nonlinear function approximation, Appendix J identifies the additional difficulty. The Jacobian of the expected update contains a term involving the Hessian of the function approximator weighted by the TD-error, i.e., ∑s,a∇2fθ(s,a)δθ(s,a)\sum_{s,a}\nabla^2 f_{\theta}(s,a)\delta_{\theta}(s,a). This term vanishes in the linear case but must be controlled in the nonlinear case. A possible direction is to analyze a neighborhood in which the nonlinear approximator remains close to its linearization. If the linearized update satisfies the SNRDD condition, sufficiently small changes in its Jacobian would preserve this condition. The discussion has been added to the conclusion and appendix of the revised manuscript.

Q3. Can some standard policy concentrability assumptions extend the off-policy to the on-policy setting?

A3. We thank the reviewer for suggesting the use of concentrability assumptions. These assumptions quantify the mismatch between the sampling distribution and the distribution induced by the target policy. Combining such bounds with our SNRDD-based or AVI-based analysis may help characterize how this mismatch affects the regularization strength required for stability. Establishing this connection would require further analysis, and we view it as a promising direction for future work. The discussion has been added to conclusion of the revised manuscript.

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

This paper studies the projected Bellman equation and the convergence properties of linear Q-learning and approximate value iteration (AVI). In particular, it extends the analysis of regularized Q-learning (RegQ) introduced by Lim and Lee (2024). The authors remove the nonnegativity and orthogonality assumptions on the feature matrix. They use contraction and ODE-based stochastic approximation theory to provide a unified convergence analysis. They also investigate the relationship between SNRDD and AVI-inspired convergence conditions, with examples where Q-learning converges while AVI does not, and vice versa.

Critical strengths

(S1) The authors provide a unified convergence analysis of tabular, linear, and regularized Q-learning through contraction theory. For regularized Q-learning, removing the nonnegativity and orthogonality assumptions on the feature matrix broadens the setting covered by Lim and Lee (2024). This framework could be useful for studying the stability and/or convergence of similar algorithms.

(S2) The extensive appendix is helpful for following the definitions, proofs, and supporting results. In my opinion, it makes the work valuable for readers who want to familiarize themselves with the algorithms considered here.

Critical weaknesses

(W1) After reading the paper, the practical usefulness of the regularization method remains unclear to me. Enforcing SNRDD establishes stability, but does not establish that the resulting policy performs well (as mentioned by the authors). I would encourage the authors to provide empirical evidence on standard benchmarks (e.g., MuJoCo or Gym environments) showing that the regularization improves stability without substantially degrading policy performance. Because, in theory, we can have a very large regularization term that satisfies SNRDD, but it would not be useful in practice.

(W2) Although some individual results are interesting, I am not convinced that these smaller extensions add up to a significant contribution. For example, the new RegQ analysis relaxes the feature assumptions, but the algorithm and the use of SNRDD already appear in the literature. The paper also contains many remarks and related observations, and it is not clear to me which results are the main contributions.

Questions for authors

(Q1) Regarding the uniqueness claim in Theorem 3.2. Condition (5) is imposed on TθT_\theta, but wouldn’t the contraction argument require a condition on FF? Even with a fixed behavior policy, the target policy may change with θ\theta, and differentiating TθθT_\theta\theta introduces additional terms that are not captured by TθT_\theta alone. Could you please clarify if this is the case?

(Q2) Can we decay the regularization coefficient during learning while retaining convergence guarantees to potentially reduce the bias in the final solution?

(Q3) (minor) In Eq. (2), should γ\gamma multiply only PΠπθP\Pi_{\pi_\theta}, rather than (PΠπθ−I)(P\Pi_{\pi_\theta}-I)? In Eq. (9), the regularization term also seems to be missing αk\alpha_k.

2 comments

W1. After reading the paper, the practical usefulness of the regularization method remains unclear to me. Enforcing SNRDD establishes stability, but does not establish that the resulting policy performs well (as mentioned by the authors). I would encourage the authors to provide empirical evidence on standard benchmarks (e.g., MuJoCo or Gym environments) showing that the regularization improves stability without substantially degrading policy performance. Because, in theory, we can have a very large regularization term that satisfies SNRDD, but it would not be useful in practice.

A1. We thank the reviewer for the constructive comments on the usefuleness of the regularization. As answered in G1 in common response, regularilzation can ceate a biased solution and causes degradation on performance. In practice, this problems can be adjusted by regularizing toward a reference parameter rather than necessarily toward zero. Specifically, we can consider a regularization form min⁡θ∣∣yk−Φθ∣∣D2+∣∣Aθ−Aθˉ∣∣M2\min_{\theta} ||y_k - \Phi\theta ||^2_D + ||A\theta-A\bar{\theta} ||^2_M where θˉ\bar{\theta} can be zero or any other reference parameter, AA can be identity or feature matrix, and MM can be some probability distribution. Using an exponential moving average of θk\theta_k as θˉ\bar{\theta} and MM to be a sampling distribution such that M(s,a)=d(s)⋅1∣A∣M(s,a)=d(s)\cdot\frac{1}{|A|}, which we call Reg-EMA-Q, we can see that regularization can help mitigate performance degradation and robust to target network update period:

GameFinal-score drop (%): DQNFinal-score drop (%): Reg-EMA-QAUC drop (%): DQNAUC drop (%): Reg-EMA-Q
Boxing165.1±12.3165.1 \pm 12.3−1.8±11.5\mathbf{-1.8 \pm 11.5}154.7±4.4154.7 \pm 4.4−2.7±4.8\mathbf{-2.7 \pm 4.8}
Breakout48.3±6.5\mathbf{48.3 \pm 6.5}50.7±9.6\mathbf{50.7 \pm 9.6}32.4±3.6\mathbf{32.4 \pm 3.6}30.5±5.4\mathbf{30.5 \pm 5.4}
Kung Fu Master100.0±0.0100.0 \pm 0.015.4±29.3\mathbf{15.4 \pm 29.3}100.0±0.0100.0 \pm 0.018.6±9.2\mathbf{18.6 \pm 9.2}
Asterix27.6±11.127.6 \pm 11.1−10.9±11.3\mathbf{-10.9 \pm 11.3}39.4±5.839.4 \pm 5.84.8±3.0\mathbf{4.8 \pm 3.0}

Values are computed as 100(1−Gˉ1/Gˉ1000)100(1-\bar{G}_{1}/\bar{G}_{1000}), where Gˉi\bar{G}_i denotes the mean final evaluation score or mean area under the curve (AUC) at target update frequency ii. Lower is better and negative values indicate improvement. The details are presented in Appendix L of the revised paper.

W2. Although some individual results are interesting, I am not convinced that these smaller extensions add up to a significant contribution. For example, the new RegQ analysis relaxes the feature assumptions, but the algorithm and the use of SNRDD already appear in the literature. The paper also contains many remarks and related observations, and it is not clear to me which results are the main contributions.

A2. We thank the reviewer for pointing out that the main contributions are not sufficiently clear. We agree that neither the RegQ algorithm nor the SNRDD condition itself is new. Our main objective is to clarify the relationship between the existence of PBE solutions and the convergence of two algorithms that seek these solutions: linear Q-learning and AVI.

First, we develop two sets of sufficient conditions for the existence and uniqueness of PBE solutions, based on SNRDD and the AVI formulation, respectively. The SNRDD-based analysis also provides a common convergence argument for tabular, linear, and regularized Q-learning (Proposition 4.4).

Second, we relate these conditions and identify structural assumptions under which they coincide (Proposition 3.13). Beyond these assumptions, we provide examples where Q-learning converges while AVI fails, and vice versa (Section 5). Thus, although the two algorithms seek solutions to the same PBE, their convergence guarantees are not interchangeable.

Finally, Section 6 examines the limitations of these guarantees under an ϵ\epsilon-greedy behavior policy. The examples show that changing the exploration parameter can alter the number of PBE solutions or introduce an unstable solution that induces an optimal policy. Together, these results distinguish solution existence, algorithmic convergence, and the quality of the induced policy.

Q3. Regarding the uniqueness claim in Theorem 3.2. Condition (5) is imposed on TθT_\theta, but wouldn’t the contraction argument require a condition on FF? Even with a fixed behavior policy, the target policy may change with , and differentiating introduces additional terms that are not captured by alone. Could you please clarify if this is the case?

A3. We thank the reviewer for the clarification on Theorem 3.2. Considering the map F~(θ)=θ+αF(θ)\tilde{F}(\theta)=\theta+\alpha F(\theta) for some small α\alpha, the contraction condition on F~(θ)−F~(θ′)\tilde{F}(\theta)-\tilde{F}(\theta') reduces to analysis on TθT_\theta and this can be established by (5). Moreover, the function is differentiable almost everywhere, and the non-differentiable terms can be handled by the Lebourg's mean value theorem provided in Appendix D of the manuscript.

Q4. Can we decay the regularization coefficient during learning while retaining convergence guarantees to potentially reduce the bias in the final solution?

A4. We thank the reviewer for the comments on the decaying regularization coefficient. This is possible together with scheduling of the exploration phase. Suppose we use ϵ\epsilon-behavior or ϵ\epsilon-softmax policy. Then, in the initial phase of the learning process, high ϵ\epsilon value is required for exploration but this can cause instability, and therefore we can use high regularization in the exploration phase, and as the learning progresses we can decay both ϵ\epsilon and the regularization so that the update becomes closer to on-policy learning as in SARSA. Then, with small ϵ\epsilon, the update can be stable without or using small regularization. We have added the discussion in page 8 of the revised manuscript.

Q5. In Eq. (2), and Eq. (9) minor errors.

A5. We thank the reviewer for pointing out these. We have fixed this in the revision.

Comments on the paper

1 comment

We thank the reviewers for the constructive comments to improve the manuscript. The changes in the manuscript has been colored blue, and we provide a common resopnse in the following:

G1. Regularization in practice

In practice, SNRDD condition can be difficult to be met, and regularilzation can ceate a biased solution and causes degradation on performance. In practice, this problems can be adjusted by regularizing toward a reference parameter rather than necessarily toward zero. Specifically, we can consider a regularization form min⁡θ∣∣yk−Φθ∣∣D2+∣∣Aθ−Aθˉ∣∣M2\min_{\theta} ||y_k - \Phi\theta ||^2_D + ||A\theta-A\bar{\theta} ||^2_M where θˉ\bar{\theta} can be zero or any other reference parameter, AA can be identity or feature matrix, and MM can be some probability distribution. Using an exponential moving average of θk\theta_k as θˉ\bar{\theta} and MM to be a sampling distribution such that M(s,a)=d(s)⋅1∣A∣M(s,a)=d(s)\cdot\frac{1}{|A|}, which we call Reg-EMA-Q, we can see that regularization can help mitigate performance degradation and is robust to target network update period choice:

GameFinal-score drop (%): DQNFinal-score drop (%): Reg-EMA-QAUC drop (%): DQNAUC drop (%): Reg-EMA-Q
Boxing165.1±12.3165.1 \pm 12.3−1.8±11.5\mathbf{-1.8 \pm 11.5}154.7±4.4154.7 \pm 4.4−2.7±4.8\mathbf{-2.7 \pm 4.8}
Breakout48.3±6.5\mathbf{48.3 \pm 6.5}50.7±9.6\mathbf{50.7 \pm 9.6}32.4±3.6\mathbf{32.4 \pm 3.6}30.5±5.4\mathbf{30.5 \pm 5.4}
Kung Fu Master100.0±0.0100.0 \pm 0.015.4±29.3\mathbf{15.4 \pm 29.3}100.0±0.0100.0 \pm 0.018.6±9.2\mathbf{18.6 \pm 9.2}
Asterix27.6±11.127.6 \pm 11.1−10.9±11.3\mathbf{-10.9 \pm 11.3}39.4±5.839.4 \pm 5.84.8±3.0\mathbf{4.8 \pm 3.0}

Values are computed as 100(1−Gˉ1/Gˉ1000)100(1-\bar{G}_{1}/\bar{G}_{1000}), where Gˉi\bar{G}_i denotes the mean final evaluation score or mean area under the curve (AUC) at target update frequency ii. Lower is better and negative values indicate improvement. The details are presented in Appendix L of the revised paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.