Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, the understanding of function approximation schemes is still largely missing. In this talk, we will discuss recent progress on understanding efficient RL algorithms with function approximation. In particular, we show that, RL problems whose optimal Q-values admit approximated linear representations can be provably hard, i.e., any algorithm solving this class of problems requires an exponential number of samples. Then we show that such an exponential barrier can be overcome by exploiting structures in the transition model: probably efficient algorithms exist for Markov decision processes with linear function approximation if the features encode model information. Lastly, we generalize algorithms in the linear setting to algorithms with general value function approximation. In particular, we show that if the value functions admit an approximation with a function class F, our algorithm achieves a regret bound of poly(dH)sqrt{T} where d is a complexity measure of  F depending on the eluder dimension, H is the planning horizon, and T is the number interactions with the environment. Our algorithm is model-free and does not make explicit assumptions on the model of the environment. It thus provides a framework to justify algorithms used in practice.