  Function approximation has been an indispensable component in modern
reinforcement learning algorithms designed to tackle problems with large state
spaces in high dimensions. This paper reviews recent results on error analysis
for these reinforcement learning algorithms in linear or nonlinear
approximation settings, emphasizing approximation error and estimation
error/sample complexity. We discuss various properties related to approximation
error and present concrete conditions on transition probability and reward
function under which these properties hold true. Sample complexity analysis in
reinforcement learning is more complicated than in supervised learning,
primarily due to the distribution mismatch phenomenon. With assumptions on the
linear structure of the problem, numerous algorithms in the literature achieve
polynomial sample complexity with respect to the number of features, episode
length, and accuracy, although the minimax rate has not been achieved yet.
These results rely on the $L^\infty$ and UCB estimation of estimation error,
which can handle the distribution mismatch phenomenon. The problem and analysis
become substantially more challenging in the setting of nonlinear function
approximation, as both $L^\infty$ and UCB estimation are inadequate for
bounding the error with a favorable rate in high dimensions. We discuss
additional assumptions necessary to address the distribution mismatch and
derive meaningful results for nonlinear RL problems.
