  Value function approximation is important in modern reinforcement learning
(RL) problems especially when the state space is (infinitely) large. Despite
the importance and wide applicability of value function approximation, its
theoretical understanding is still not as sophisticated as its empirical
success, especially in the context of general function approximation. In this
paper, we propose a provably efficient RL algorithm (both computationally and
statistically) with general value function approximations. We show that if the
value functions can be approximated by a function class that satisfies the
Bellman-completeness assumption, our algorithm achieves an
$\widetilde{O}(\text{poly}(\iota H)\sqrt{T})$ regret bound where $\iota$ is the
product of the surprise bound and log-covering numbers, $H$ is the planning
horizon, $K$ is the number of episodes and $T = HK$ is the total number of
steps the agent interacts with the environment. Our algorithm achieves
reasonable regret bounds when applied to both the linear setting and the sparse
high-dimensional linear setting. Moreover, our algorithm only needs to solve
$O(H\log K)$ empirical risk minimization (ERM) problems, which is far more
efficient than previous algorithms that need to solve ERM problems for
$\Omega(HK)$ times.
