A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces
By Omar Darwiche Domingues, Pierre M'enard, Matteo Pirotta, Emilie Kaufmann, Michal Valko. 2020
45 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, General Decision Sciences
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Matthew Riemer
- Irina Rish
- Doina Precup
- Sergey Levine
- Khimya Khetarpal
- Pascal Vincent
- Ahmed Touati
- Yoshua Bengio
Citations in the corpus
- Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “In this framework, it then possible to consider assumptions around variation budgets in tabular (Cheung et al., 2020; Domingues et al., 2020) and linear function (Touati and Vincent, 2020) MDPs to improve learning in the face of non-stationarity.”
- Efficient Learning in Non-Stationary Linear Markov Decision Processes (2020, background): “Comparing to the bound Õ(|S||A|H(2)∆K) proved in Domingues et al. (2020) in the tabular setting, both bounds share the same dependence in terms of ∆, H and K but our bound has an extra factor of |S||A|.”
- Near-Optimal Model-Free Reinforcement Learning in Non-Stationary Episodic MDPs (2021, methodology): “We measure the optimality of the policy π in terms of its dynamic regret (Cheung et al., 2020; Domingues et al., 2020), which compares the agent’s policy with the optimal policy of each individual episode in hindsight: where the initial state s m 1 of each episode is chosen by an oblivious…”