A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces
Omar Darwiche Domingues, Pierre Menard, Matteo Pirotta, Emilie Kaufmann, Michal Valko
Abstract
In this work, we propose KeRNS: an algorithm for episodic reinforcement learning in non-stationary Markov Decision Processes (MDPs) whose state-action set is endowed with a metric. Using a non-parametric model of the MDP built with time-dependent kernels, we prove a regret bound that scales with the covering dimension of the state-action space and the total variation of the MDP with time, which quantifies its level of non-stationarity. Our method generalizes previous approaches based on sliding windows and exponential discounting used to handle changing environments. We further propose a practical implementation of KeRNS, we analyze its regret and validate it experimentally.
BibTeX
@InProceedings{pmlr-v130-darwiche-domingues21a,
title = { A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces },
author = {Darwiche Domingues, Omar and Menard, Pierre and Pirotta, Matteo and Kaufmann, Emilie and Valko, Michal},
booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics},
pages = {3538--3546},
year = {2021},
editor = {Banerjee, Arindam and Fukumizu, Kenji},
volume = {130},
series = {Proceedings of Machine Learning Research},
month = {13--15 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v130/darwiche-domingues21a/darwiche-domingues21a.pdf},
url = {https://proceedings.mlr.press/v130/darwiche-domingues21a.html},
abstract = { In this work, we propose KeRNS: an algorithm for episodic reinforcement learning in non-stationary Markov Decision Processes (MDPs) whose state-action set is endowed with a metric. Using a non-parametric model of the MDP built with time-dependent kernels, we prove a regret bound that scales with the covering dimension of the state-action space and the total variation of the MDP with time, which quantifies its level of non-stationarity. Our method generalizes previous approaches based on sliding windows and exponential discounting used to handle changing environments. We further propose a practical implementation of KeRNS, we analyze its regret and validate it experimentally. }
}