- 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
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.
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 where θˉ can be zero or any other reference parameter, A can be identity or feature matrix, and M can some probability distribution. Using an exponential moving average of θk as θˉ and M to be a sampling distribution such that M(s,a)=d(s)⋅∣A∣1, 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:
Values are computed as 100(1−Gˉ1/Gˉ1000), where Gˉi denotes the mean final evaluation score or mean area under the curve (AUC) at target update frequency i. 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)