Timezone: »

 
Spotlight
Kernel-Based Reinforcement Learning: A Finite-Time Analysis
Omar Darwiche Domingues · Pierre Menard · Matteo Pirotta · Emilie Kaufmann · Michal Valko

Wed Jul 21 06:45 AM -- 06:50 AM (PDT) @ None
in Algorithms and Applications »
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. For problems with $K$ episodes and horizon $H$, we provide a regret bound of $\widetilde{O}\left( H^3 K^{\frac{2d}{2d+1}}\right)$, 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 applies to a wide range of tasks. We empirically validate our approach in continuous MDPs with sparse rewards.
Keywords: Theory -> RL, Decisions and Control Theory

Author Information

Omar Darwiche Domingues (Inria)
Pierre Menard (Inria)
Matteo Pirotta (Facebook AI Research)
Emilie Kaufmann (CNRS, Univ. Lille, Inria)
Michal Valko (DeepMind / Inria / ENS Paris-Saclay)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors