Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides a theoretical study of the successful deep Q-networks (DQN) framework under an online, episodic Markov decision process (MDP) model with T episodes. They focus on Besov and Barron function spaces in approximating an $\alpha$ smooth Q-function in a d-dimensional feature space. Under some assumptions, they prove that DQN with shallow layers and medium width can learn the MDP with sublinear regret.
strengths_and_weaknesses: Strengths:
In summary, this is a good paper for RL theory. It tries to give a theoretical understanding of the widely used DQN algorithm, which is fundamental in Deep RL. The theoretical results in this paper is also interesting. It shows that DQN-type algorithm can achieve sublinear regret using a small-scale neural network, under some assumptions. As far as I know, these results are novel in RL theory. Also, the results match the practical experience.

Weaknesses:
1. The algorithm requires optimizing a neural network function to minimum. However in practice, it is usually not achievable. What will the results be if we only have an approximate solution to the optimization problem?

questions: 1. In practice, how large is the norm parameter B?
2. I do not understand why the regret bound in Theorem 1 not depend on dimension $d$ but in Theorem 2 it depends on $d$ explicitly. What is the reason behind such difference?
3. What is the role of sparsity parameter $S$ defined in Eq. (5)?

limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper theoretically studies value iteration type algorithms in RL using neural networks belonging to either the Besov or Barron function spaces. Under the probabilistic sufficient exploration assumption, scalings of the width and depth of the neural network are revealed for achieving sublinear regret for the proposed least square value iteration with neural networks. It is argued that the width has a more prominent effect than depth. Quantitative regret bound is established and only depends logarithmically on the dimension $d$.
strengths_and_weaknesses: This paper is easy to follow, and it is an important topic to analyze RL algorithms that employ neural network type estimators. The algorithm studied in this paper (Algorithm 1) is well-known, while it is claimed that the theoretical analysis reveals guidelines for the training setup in real applications. The discussion about related works for RL with function approximation can be more detailed, especially comparing the difference between the assumptions on the function classes. Also, it seems that some existing literature on theoretical analysis of Q-learning algorithms is missing, e.g., [1] and [2].



Reference:

[1] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, Michael I. Jordan. Is Q-learning Provably Efficient?

[2] Pan Xu, Quanquan Gu. A finite-time analysis of Q-learning with neural network function approximation.
questions: Some comments and questions are as follows:

1. There is a mismatch between the terminology 'Q-learning' and the actual algorithm studied in this paper, which is indeed a least square value iteration algorithm with a neural network estimator. This is different from the usual Q-learning type algorithm, where the Q updates correspond to gradient descent of one-step TD error. This should be clarified in the paper.
2. The regret bounds in Theorem 1 and 2 scale with $T^{4/3}$ and $T^{\frac{\alpha+d}{2\alpha+d}}$, which are strictly worse than $\sqrt{T}$. Do these results degenerate to $\sqrt{T}$-type bound under simpler settings such as linear function approximation?
3. Why there is no need to do exploration in Algorithm 1? It should be necessary for online RL algorithms. Is this due to the PSE assumption?
4. Indeed, the PSE assumption seems unclear to me. In the definition of $\mathcal{G}_\epsilon$, is $f$ an arbitrary function? Here $\epsilon$ seems to depend on the value of $\|f\|_\infty$, and it is unclear where $f$ is specified. Apart from this, by letting $\bar\mu_h^t(\mathcal{G}_\epsilon) > 0$ hold with probability at least $1-\delta$, it is imposing some condition on $\widehat Q_h^1, \ldots, \widehat Q_h^T$, which is obtained in an online manner. Then, conditioning on Assumption 1 being true, $\{\widehat Q_h^t\}$ is not a martingale sequence any more as conditioning changes its distribution (so do the TD error), thus it needs to be justified how to use martingale concentration inequalities (line 307-308).
5. When running Algorithm 1, the collected data is conditionally independent instead of independent, because the policy in episode $t$ depends on all the previous data. Then how can we apply Lemma 5/6 (line 320-321)? 
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies a deep Q-network algorithm in the online and episodic MDP setting. With the probabilistic sufficient exploration assumption, this paper focuses on Besov and Barron function spaces to model the deep Q-networks. Two main theoretical guarantees are provided: one is for shadow neural networks, and the other is for deep neural networks. In both two cases, sublinear regret is achieved. From the theoretical results, this paper claims that for low smooth Q-functions, the width has a more important role and a constant depth is enough. From this perspective, this paper may shed light on width and depth guidelines in deep Q-learning. 

===

After rebuttal, my concerns are addressed. This paper may shed new light on understanding deep neural networks in reinforcement learning. Yet, there are several future works, as noted in the conclusion part. Therefore, I change my score from 4 to 6. 
strengths_and_weaknesses: **Strengths**

- More border function classes are considered. Most prior works focus on the linear function approximation or (limited) non-linear function approximation.
- A tighter bound in terms of the dependence on the width and depth is provided. For the prior work that relies on NTK, an impractical width $m = \Omega(T^{13}) $is required.

**Weakness**

- The whole theory heavily relies on the assumption of probabilistic sufficient exploration. With this assumption, the exploration issue is already addressed. To this end, it is unclear why this paper studies the function approximation in the online setting. It seems that the offline setting considered in [1] is sufficient to study how to approximate optimal Q-value functions. 
- To my knowledge, the value iteration algorithm (with neural networks) is rarely used in practice, meaning that a gap separates the theory in this paper from practical algorithms. To clarify, Algorithm 1 has two computational issues. First, it is hard to compute the global minimizer defined in the empirical objective (i.e., Equation (3)) for each iteration. The computation cost is unacceptable. Therefore, people prefer iterative algorithms like Q-learning. Second, Q-learning with function approximation can easily diverge, and the target network is introduced to address this issue in DQN. However, these features are not captured by Algorithm 1 and theoretical results.

[1] Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning. In Learning for Dynamics and Control, pages 486–489, 2020.

questions: I have a few concerns about this paper's motivation and theoretical implications. I list my questions as follows. 

1. Can the authors justify the (technical) challenge after Assumption 1 is satisfied? 

I have this question because I believe how to address the exploration-and-exploitation trade-off is the core of online learning. However, if we make the so-called Probabilistic sufficient exploration, it is not clear (at least for me) what is challenging in this setting. It seems that it is sufficient to consider the offline setting, where a fixed dataset is provided, to study how to approximate optimal Q-value functions. I guess that the online setting considered in this paper may introduce unnecessary (technical) challenges. I would appreciate it if the authors could help clarify this point.

2. Can the authors further explain the empirical objective in Equation (3)?

It is known that DQN has two key components: experience replay and the target network. Without the target network, Q-learning with function approximation can easily diverge in theory; see [2] and Section 11.3 of [3]. From the workshop paper [4] to the nature version, the target network is introduced, and the performance is improved a lot for DQN. In practice, if the target network is removed, it is easy to see that DQN cannot work for games like Pong and Breakout. 

This paper shows that i.i.d. sampling by experience replay is not necessary. This is acceptable. Then, this paper further studies Algorithm 1, where the target network is not used. This is a huge difference with practice. With a powerful approximation power, it is not very surprising that Algorithm 1 can converge. However, the issue is that the computation cost of Algorithm 1 is huge, which restricts the application of Algorithm 1. Based on this thought, I am not convinced that the theoretical implications in this paper are well-aligned with practical observations.  Please also refer to [5] for the study of online target Q-learning (authors are excused for this paper because this paper is recently posted).

[2] Baird, Leemon. "Residual algorithms: Reinforcement learning with function approximation." *Machine Learning Proceedings 1995*. Morgan Kaufmann, 1995. 30-37. 

[3] Sutton, Richard S., and Andrew G. Barto. *Reinforcement learning: An introduction*. MIT press, 2018.

[4] Mnih, Volodymyr, et al. "Playing atari with deep reinforcement learning." *arXiv preprint arXiv:1312.5602* (2013).

[5] Zanette, Andrea, and Martin J. Wainwright. "Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning." arXiv preprint arXiv:2206.00796 (2022).
limitations: This paper does a great job of analyzing Q-learning with deep neural networks. The main limitations are listed below. 

- Assumption 1 is quite strong for studying online learning. Though this paper explains that epsilon-greedy can achieve this, it is known that epsilon-greedy is much inefficient. 
- A gap between Algorithm 1 and practical one (i.e., the target network is not considered). It is hard for me to believe the theoretical implications in this paper are well-aligned with practical observations. If the authors can provide some numerical results to justify the theoretical results, I would be much convinced. 

I would suggest that the authors can elaborate on the technical challenge and provide more justification for the setting studied in this paper. 

**Minor Issues**

This writing of this paper can be further improved, as there are several grammar errors. To name a few,

- In Line 35, demonstrates -> demonstrate
- In Line 82, effects -> affects 
- In Line 93, assuming a simulator can require any state and action -> assuming a simulator in which the agent can require any state and action
- In Line 99, the above algorithms -> the above bounds 
- In Line 112, function spaces of two -> and function spaces of two 
- In Line 177, which not heavily depends on -> which does not heavily depend on 
- In Line 190, $\ell_1$ path norm -> $\ell_1$-path norm 
- In Line 206, it is not clear the meaning of "this requirement"
- In Line 251, they -> [12]
review_title: null

Meta-review: metareview: This paper provides a theoretical study of the successful deep Q-networks framework under an online, episodic Markov decision process (MDP) model with T episodes. All reviewers and the AC believe this is a solid RL theory paper.
confidence: Certain
Decision: Accept