HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Kernel-based reinforcement Learning: A finite-time analysis

Omar Domingues 1 Pierre Ménard 2 Matteo Pirotta 3 Emilie Kaufmann 1 Michal Valko 4
1 Scool - Scool
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning problems whose state-action space is endowed with a metric. We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards and transitions to efficiently balance exploration and exploitation. Unlike existing approaches with regret guarantees, it does not use any kind of partitioning of the state-action space. For problems with $K$ episodes and horizon $H$, we provide a regret bound of O H 3 K max(1 2 , 2d 2d+1) , where $d$ is the covering dimension of the joint state-action space. This is the first regret bound for kernel-based RL using smoothing kernels, which requires very weak assumptions on the MDP and has been previously applied to a wide range of tasks. We empirically validate our approach in continuous MDPs with sparse rewards.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-02541790
Contributor : Michal Valko Connect in order to contact the contributor
Submitted on : Friday, July 16, 2021 - 3:23:10 PM
Last modification on : Thursday, March 24, 2022 - 3:43:17 AM

File

domingues2021kernel-based.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02541790, version 2

Citation

Omar Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, Michal Valko. Kernel-based reinforcement Learning: A finite-time analysis. International Conference on Machine Learning, Jul 2021, Vienna / Virtual, Austria. ⟨hal-02541790v2⟩

Share

Metrics

Record views

142

Files downloads

195