Provably Efficient Kernelized Q-Learning

• URL: http://arxiv.org/abs/2204.10349v1
• Date: Thu, 21 Apr 2022 18:08:22 GMT
• Title: Provably Efficient Kernelized Q-Learning
• Authors: Shuang Liu and Hao Su
• Abstract summary: We propose and analyze a kernelized version of Q-learning. We derive regret bounds for arbitrary kernels. We test our algorithm on a suite of classic control tasks.
• Score: 26.37242007290973
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose and analyze a kernelized version of Q-learning. Although a kernel space is typically infinite-dimensional, extensive study has shown that generalization is only affected by the effective dimension of the data. We incorporate such ideas into the Q-learning framework and derive regret bounds for arbitrary kernels. In particular, we provide concrete bounds for linear kernels and Gaussian RBF kernels; notably, the latter bound looks almost identical to the former, only that the actual dimension is replaced by a different notion of dimensionality. Finally, we test our algorithm on a suite of classic control tasks; remarkably, under the Gaussian RBF kernel, it achieves reasonably good performance after only 1000 environmental steps, while its neural network counterpart, deep Q-learning, still struggles.

Related papers

• Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel [55.82768375605861]
  We establish a generalization bound for gradient flow that aligns with the classical Rademacher complexity for kernel methods.<n>Unlike static kernels such as NTK, the LPK captures the entire training trajectory, adapting to both data and optimization dynamics.
  arXiv  Detail & Related papers  (2025-06-12T23:17:09Z)
• Scalable Gaussian Processes with Low-Rank Deep Kernel Decomposition [7.532273334759435]
  Kernels are key to encoding prior beliefs and data structures in Gaussian process (GP) models.<n>Deep kernel learning enhances kernel flexibility by feeding inputs through a neural network before applying a standard parametric form.<n>We introduce a fully data-driven, scalable deep kernel representation where a neural network directly represents a low-rank kernel.
  arXiv  Detail & Related papers  (2025-05-24T05:42:11Z)
• Learning Analysis of Kernel Ridgeless Regression with Asymmetric Kernel Learning [33.34053480377887]
  This paper enhances kernel ridgeless regression with Locally-Adaptive-Bandwidths (LAB) RBF kernels. For the first time, we demonstrate that functions learned from LAB RBF kernels belong to an integral space of Reproducible Kernel Hilbert Spaces (RKHSs)
  arXiv  Detail & Related papers  (2024-06-03T15:28:12Z)
• On the Sublinear Regret of GP-UCB [58.25014663727544]
  We show that the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm enjoys nearly optimal regret rates. Our improvements rely on a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel.
  arXiv  Detail & Related papers  (2023-07-14T13:56:11Z)
• Neural Networks with Sparse Activation Induced by Large Bias: Tighter Analysis with Bias-Generalized NTK [86.45209429863858]
  We study training one-hidden-layer ReLU networks in the neural tangent kernel (NTK) regime. We show that the neural networks possess a different limiting kernel which we call textitbias-generalized NTK We also study various properties of the neural networks with this new kernel.
  arXiv  Detail & Related papers  (2023-01-01T02:11:39Z)
• Learning "best" kernels from data in Gaussian process regression. With application to aerodynamics [0.4588028371034406]
  We introduce algorithms to select/design kernels in Gaussian process regression/kriging surrogate modeling techniques. A first class of algorithms is kernel flow, which was introduced in a context of classification in machine learning. A second class of algorithms is called spectral kernel ridge regression, and aims at selecting a "best" kernel such that the norm of the function to be approximated is minimal.
  arXiv  Detail & Related papers  (2022-06-03T07:50:54Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  We show that a phenomenon can be precisely characterized in the context of kernel methods. We consider the minimization of a quadratic objective in a separable Hilbert space, and show that with early stopping, the choice of learning rate influences the spectral decomposition of the obtained solution.
  arXiv  Detail & Related papers  (2022-02-28T13:01:04Z)
• Meta-Learning Hypothesis Spaces for Sequential Decision-making [79.73213540203389]
  We propose to meta-learn a kernel from offline data (Meta-KeL) Under mild conditions, we guarantee that our estimated RKHS yields valid confidence sets. We also empirically evaluate the effectiveness of our approach on a Bayesian optimization task.
  arXiv  Detail & Related papers  (2022-02-01T17:46:51Z)
• Random Features for the Neural Tangent Kernel [57.132634274795066]
  We propose an efficient feature map construction of the Neural Tangent Kernel (NTK) of fully-connected ReLU network. We show that dimension of the resulting features is much smaller than other baseline feature map constructions to achieve comparable error bounds both in theory and practice.
  arXiv  Detail & Related papers  (2021-04-03T09:08:12Z)
• End-to-end Kernel Learning via Generative Random Fourier Features [31.57596752889935]
  Random Fourier features (RFFs) provide a promising way for kernel learning in a spectral case. In this paper, we consider a one-stage process that incorporates the kernel learning and linear learner into a unifying framework.
  arXiv  Detail & Related papers  (2020-09-10T00:27:39Z)
• Finite Versus Infinite Neural Networks: an Empirical Study [69.07049353209463]
  kernel methods outperform fully-connected finite-width networks. Centered and ensembled finite networks have reduced posterior variance. Weight decay and the use of a large learning rate break the correspondence between finite and infinite networks.
  arXiv  Detail & Related papers  (2020-07-31T01:57:47Z)
• Avoiding Kernel Fixed Points: Computing with ELU and GELU Infinite Networks [12.692279981822011]
  We derive the covariance functions of multi-layer perceptrons with exponential linear units (ELU) and Gaussian error linear units (GELU) We analyse the fixed-point dynamics of iterated kernels corresponding to a broad range of activation functions. We find that unlike some previously studied neural network kernels, these new kernels exhibit non-trivial fixed-point dynamics.
  arXiv  Detail & Related papers  (2020-02-20T01:25:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.