- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes Q-Hankeling, which regularizes the Q-function approximator using an autoregressive proxy to encourage effective low Hankel-rank along the temporal axis. This is motivated by the observation that the Hankel rank (of the Q-values along a trajectory) tends to decrease over the course of training. The authors integrate Q-Hankeling into DQN, SAC, and TD3, and report improved performance across various environments in standard benchmarks.
Critical strengths
The paper identifies an interesting pattern that Q-values along trajectories tend to have decreasing effective Hankel rank during training across several environments. It also proposes a practical way to exploit this observation through a learned autoregressive penalty, avoiding explicit Hankel-matrix construction. The regularizer integrates readily into several established RL algorithms, and the reported gains across many evaluated settings support its practical utility.
Critical weaknesses
Since the Hankel matrices are constructed from learned critic outputs along trajectories, the observed rank decrease is entangled by properties of the function approximator, changes in the visited trajectories, or structure in the underlying policy values. The experiments do not isolate these explanations. An experiment using MC rollouts can partially address this. This also leaves the applicability of the proposed regularizer somewhat unclear. If the true Q-value sequences do not admit a low rank structure, is this regularization still beneficial?
More broadly, the RL interpretation of the regularizer remains underdeveloped. Although it explicitly encourages critic outputs to follow a shared linear recurrence, it is unclear what desirable property of value estimation or policy learning this penalty encourages. The reported performance gains demonstrate usefulness in several settings, but do not establish the underlying mechanism.
Questions for authors
- From an RL perspective (given the true q-values), what are the implications of the Hankel rank?
- What explains the observed low effective Hankel rank? Since the measurements use learned Q-functions under evolving policies, can the authors distinguish structure in true policy values from effects of function approximation and changes in visited trajectories?
3 comments
Q2: On critic and visitation effects
Our rollout diagnostics freeze the policy and critic at each checkpoint and collect fresh evaluation trajectories (Section 4.2 and Appendix D.3). This avoids policy changes within each evaluation, but both the critic and the trajectory distribution can change across checkpoints. As training approaches convergence, the policy and critic may stabilize, bringing the learning process closer to the fixed-policy setting considered in Section 4.3. This offers a possible connection between the analysis and late-training behavior, although a stable critic need not equal the true policy values, and the mixing assumptions remain additional conditions. These measurements alone therefore cannot separate structure in true policy values from approximation and visitation effects. Following the reviewer's suggestion, we conducted this control on Classical Control with the baseline DQN (five seeds). At each checkpoint, we compare the critic predictions with the discounted returns along greedy evaluation trajectories. Since policy and dynamics are deterministic, these returns equal exactly on trajectories that terminate. The three tasks of the paper have a constant reward at every step, so their returns have low Hankel rank under any policy, and we therefore consider an Acrobot variant with a dense reward (Table G below). There, the Monte Carlo estimates have low normalized Hankel rank throughout training, whereas the critic predictions at initialization do not. As training proceeds, the critic predictions closely match the Monte Carlo estimates and their rank decreases, remaining at least as large as the Monte Carlo rank on 284 of 285 trajectories after the first 5,000 steps. This is empirical evidence that, in this setting, the low-rank structure is present in the true policy values and not introduced by function approximation. The evidence is limited to DQN on small deterministic tasks, and extending the control to MuJoCo and Atari-100k remains open. We will include this control in the revised manuscript.
Table G. Monte Carlo control on Acrobot with a dense reward, using the baseline DQN and five seeds. Entries are medians over greedy rollouts that terminate. Ranks are effective Hankel ranks at 99.9% energy divided by the matrix dimension. Correlation is between the critic predictions and the Monte Carlo estimates along a rollout.
| Training | Rollouts | Critic rank | Monte Carlo rank | Correlation |
|---|---|---|---|---|
| Start | 10 | 0.471 | 0.022 | 0.772 |
| 25% | 75 | 0.146 | 0.077 | 0.998 |
| 50% | 75 | 0.136 | 0.075 | 0.999 |
| 75% | 75 | 0.139 | 0.083 | 0.999 |
| 100% | 30 | 0.134 | 0.095 | 0.999 |
Thank you for the reply. My questions have been addressed, and I've adjusted the score accordingly. I think the new experiments are valuable in understanding the cause of this phenomenon, and I encourage the authors to add more discussions on what properties of the MDP could be causing this.
We thank the reviewer for their comments, which will help us improve the manuscript.
W1: Where does low-rank Hankel structure come from?
Explaining why low-rank Hankel structure emerges during critic learning remains open. As discussed in our response to Reviewer QoJW, W1, Theorem 4.1 motivates the recurrence penalty, while Theorem 4.2 investigates mixing as a possible explanation for the structure under a stationary policy and exact values. These insights provide useful guidance, but our rollout measurements alone do not disentangle true-value structure from function approximation and visitation effects. We refer the reviewer to that response for the supporting evidence and theoretical limitations, and to Q2 below for a Monte Carlo control on Classical Control. Whether the regularizer remains beneficial when true value sequences lack this structure is also unresolved.
W2: On the role of the regularizer
Q-Hankeling aims to encourage low-rank Hankel structure in critic predictions through a low-order recurrence penalty, motivated by Theorem 4.1. The Hankel diagnostics in Appendix E.4.3 provide empirical evidence that it encourages this structure on replay windows by the end of training, alongside the aggregate performance improvements reported in Tables 1 and 2 of the manuscript. These findings support the usefulness of encouraging low-rank Hankel structure through the recurrence penalty motivated by Theorem 4.1. In Q1, we discuss how this structural bias may improve sample efficiency by reducing the effective complexity of critic learning. We will clarify this interpretation in the revised manuscript.
Q1: Implications of low-rank Hankel structure
For a fixed policy, low Hankel rank means that its values along a trajectory admit a compact recurrence description. Under the assumptions of Theorem 4.1, approximate low rank is equivalent to an approximate low-order linear recurrence, with conditioning factors controlling the approximation. From an RL perspective, this suggests an inductive bias for value estimation: if policy values approximately satisfy low-order recurrences, encouraging this property may reduce the effective complexity of critic learning without excluding accurate value predictions. This motivation is consistent with RL theory connecting sample efficiency to suitable complexity measures of value-function classes under additional assumptions, such as the Bellman Eluder dimension [2]. We have not established that low Hankel rank controls these complexity measures; proving a sample-complexity benefit for Q-Hankeling remains an open question.
[2] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms. NeurIPS, 2021.