  This paper provides a theoretical study of deep neural function approximation
in reinforcement learning (RL) with the $\epsilon$-greedy exploration under the
online setting. This problem setting is motivated by the successful deep
Q-networks (DQN) framework that falls in this regime. In this work, we provide
an initial attempt on theoretical understanding deep RL from the perspective of
function class and neural networks architectures (e.g., width and depth) beyond
the ``linear'' regime. To be specific, we focus on the value based algorithm
with the $\epsilon$-greedy exploration via deep (and two-layer) neural networks
endowed by Besov (and Barron) function spaces, respectively, which aims at
approximating an $\alpha$-smooth Q-function in a $d$-dimensional feature space.
We prove that, with $T$ episodes, scaling the width $m =
\widetilde{\mathcal{O}}(T^{\frac{d}{2\alpha + d}})$ and the depth
$L=\mathcal{O}(\log T)$ of the neural network for deep RL is sufficient for
learning with sublinear regret in Besov spaces. Moreover, for a two layer
neural network endowed by the Barron space, scaling the width
$\Omega(\sqrt{T})$ is sufficient. To achieve this, the key issue in our
analysis is how to estimate the temporal difference error under deep neural
function approximation as the $\epsilon$-greedy exploration is not enough to
ensure ``optimism''. Our analysis reformulates the temporal difference error in
an $L^2(\mathrm{d}\mu)$-integrable space over a certain averaged measure $\mu$,
and transforms it to a generalization problem under the non-iid setting. This
might have its own interest in RL theory for better understanding
$\epsilon$-greedy exploration in deep RL.
