Kernelized Reinforcement Learning with Order Optimal Regret Bounds
This work addresses the challenge of scaling reinforcement learning to complex, high-dimensional environments for researchers and practitioners, representing a strong specific gain rather than a foundational breakthrough.
The paper tackles the problem of reinforcement learning in large state-action spaces with general value functions by proposing π-KRVI, an optimistic modification of least-squares value iteration using kernel ridge regression. It achieves order-optimal regret guarantees, showing a significant polynomial improvement over state-of-the-art methods, with sublinear regret bounds for non-smooth kernels like Matérn kernels.
Reinforcement learning (RL) has shown empirical success in various real world settings with complex models and large state-action spaces. The existing analytical results, however, typically focus on settings with a small number of state-actions or simple models such as linearly modeled state-action value functions. To derive RL policies that efficiently handle large state-action spaces with more general value functions, some recent works have considered nonlinear function approximation using kernel ridge regression. We propose $π$-KRVI, an optimistic modification of least-squares value iteration, when the state-action value function is represented by a reproducing kernel Hilbert space (RKHS). We prove the first order-optimal regret guarantees under a general setting. Our results show a significant polynomial in the number of episodes improvement over the state of the art. In particular, with highly non-smooth kernels (such as Neural Tangent kernel or some Matérn kernels) the existing results lead to trivial (superlinear in the number of episodes) regret bounds. We show a sublinear regret bound that is order optimal in the case of Matérn kernels where a lower bound on regret is known.