  Deep Q-learning based algorithms have been applied successfully in many
decision making problems, while their theoretical foundations are not as well
understood. In this paper, we study a Fitted Q-Iteration with two-layer ReLU
neural network parameterization, and find the sample complexity guarantees for
the algorithm. Our approach estimates the Q-function in each iteration using a
convex optimization problem. We show that this approach achieves a sample
complexity of $\tilde{\mathcal{O}}(1/\epsilon^{2})$, which is order-optimal.
This result holds for a countable state-spaces and does not require any
assumptions such as a linear or low rank structure on the MDP.
