In this work, we identify a novel set of conditions that ensure convergence with probability 1 of Q-learning with linear function approximation, by proposing a two time-scale variation thereof. In the faster time scale, the algorithm features an update similar to that of DQN, where the impact of bootstrapping is attenuated by using a Q-value estimate akin to that of the target network in DQN. The slower time-scale, in turn, can be seen as a modified target network update. We establish the convergence of our algorithm, provide an error bound and discuss our results in light of existing convergence results on reinforcement learning with function approximation. Finally, we illustrate the convergent behavior of our method in domains where standard Q-learning has previously been shown to diverge.

Weaknesses: - While the theoretical results seem correct, it is not clear to me the advantages of this approach compared to previous work, in particular, gradient Q-learning (GQ). On line 110, it is written that the assumptions are not as stringent but I am not convinced that this is the case. Could the authors clarify this point? If I am interpreting it correctly, it assumes that we have a fixed replay buffer of data on which we are doing updates, as in the offline batch RL setting. It is not specified which policy is used to collect this data and I would expect certain assumptions on this behavior policy.

This paper presents a new objective and an algorithm, which is similar to DQN, that optimises for that objective. Similar to prior work (GTD, TDC, GQ), the algorithm is shown to be convergent under linear function approximation. Because the objective is different, the paper could have better illustrated what this means in terms of the quality of the fixed point the new algorithm converges to - this is only discussed in detail in a special case of a diagonal feature covariance matrix. The author response did not lift this concern, and it remains unclear whether the new algorithm has major benefits over existing related work. The experiments were deemed somewhat insufficient to fully convince the reviewers of this.

In this work, we identify a novel set of conditions that ensure convergence with probability 1 of Q-learning with linear function approximation, by proposing a two time-scale variation thereof. In the faster time scale, the algorithm features an update similar to that of DQN, where the impact of bootstrapping is attenuated by using a Q-value estimate akin to that of the target network in DQN. The slower time-scale, in turn, can be seen as a modified target network update. We establish the convergence of our algorithm, provide an error bound and discuss our results in light of existing convergence results on reinforcement learning with function approximation. Finally, we illustrate the convergent behavior of our method in domains where standard Q-learning has previously been shown to diverge.