Sample Complexity of Kernel-Based Q-Learning

2023/02/01 by Sing-Yuan Yeh, Yeh, Sing-Yuan, Fu‐Chieh Chang +9
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.2302.00727

openalex publication_date 2023/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Modern reinforcement learning (RL) often faces an enormous state-action space. Existing analytical results are typically for settings with a small number of state-actions, or simple models such as linearly modeled Q-functions. To derive statistically efficient RL policies handling large state-action spaces, with more general Q-functions, some recent works have considered nonlinear function approximation using kernel ridge regression. In this work, we derive sample complexities for kernel based Q-learning when a generative model exists. We propose a nonparametric Q-learning algorithm which finds an ε-optimal policy in an arbitrarily large scale discounted MDP. The sample complexity of the proposed algorithm is order optimal with respect to ε and the complexity of the kernel (in terms of its information gain). To the best of our knowledge, this is the first result showing a finite sample complexity under such a general model.

Related

• Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning
• A Finite Sample Complexity Bound for Distributionally Robust Q-learning
• 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
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation