An $L^2$ Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximation (CSIAM Transactions on Applied Mathematics, 2022)
Reinforcement learning (RL) algorithms based on high-dimensional function approximation have achieved tremendous empirical success in large-scale problems with an enormous number of states. However, most analysis of such algorithmsgives rise to error bounds that involve either the number of states or the numberof features. This paper considers the situation where the function approximation ismade either using the kernel method or the two-layer neural network model, in thecontext of a fitted Q-iteration algorithm with explicit regularization. We establish an $\tilde{O}(H^3|\mathcal{A}|^{\frac{1}{4}} n^{-\frac{1}{4}})$ bound for the optimal policy with $Hn$ samples, where $H$ is the lengthof each episode and $|\mathcal{A}|$ is the size of action space. Our analysis hinges on analyzingthe $L^2$ error of the approximated Q-function using $n$ data points. Even though thisresult still requires a finite-sized action space, the error bound is independent of thedimensionality of the state space.