Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Regret bounds for kernel-based reinforcement learning

Omar Domingues 1, 2 Pierre Ménard 1, 2 Matteo Pirotta 3 Emilie Kaufmann 1, 2 Michal Valko 4
1 SEQUEL - Sequential Learning
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
2 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. We empirically validate Kernel-UCBVI on discrete and continuous MDPs.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-02541790
Contributor : Michal Valko <>
Submitted on : Tuesday, April 14, 2020 - 10:47:43 AM
Last modification on : Monday, March 1, 2021 - 4:42:46 PM

File

MAIN_ARXIV.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02541790, version 1

Citation

Omar Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, Michal Valko. Regret bounds for kernel-based reinforcement learning. 2020. ⟨hal-02541790⟩

Share

Metrics

Record views

125

Files downloads

439