Reinforcement Learning with Function Approximation: From Linear to Nonlinear

Abstract

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.

References in corpus (19)

• Trust Region Policy Optimization
• High-Dimensional Continuous Control Using Generalized Advantage Estimation
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Information-Theoretic Considerations in Batch Reinforcement Learning
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Bridging RL Theory and Practice with the Effective Horizon
• An $L^2$ Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximation
• Perturbational Complexity by Distribution Mismatch: A Systematic Analysis of Reinforcement Learning in Reproducing Kernel Hilbert Space

Cited by in corpus (1)

• Graph Exploration for Effective Multi-agent Q-Learning