Online Learning in Kernelized Markov Decision Processes
arXiv:1805.08052
Abstract
We consider online learning for minimizing regret in unknown, episodic Markov decision processes (MDPs) with continuous states and actions. We develop variants of the UCRL and posterior sampling algorithms that employ nonparametric Gaussian process priors to generalize across the state and action spaces. When the transition and reward functions of the true MDP are members of the associated Reproducing Kernel Hilbert Spaces of functions induced by symmetric psd kernels (frequentist setting), we show that the algorithms enjoy sublinear regret bounds. The bounds are in terms of explicit structural parameters of the kernels, namely a novel generalization of the information gain metric from kernelized bandit, and highlight the influence of transition and reward function structure on the learning performance. Our results are applicable to multidimensional state and action spaces with composite kernel structures, and generalize results from the literature on kernelized bandits, and the adaptive control of parametric linear dynamical systems with quadratic costs.
arXiv comment22nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019
References in corpus (9)
- Safe Model-based Reinforcement Learning with Stability Guarantees
- (More) Efficient Reinforcement Learning via Posterior Sampling
- REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
- Finite-Time Analysis of Kernelised Contextual Bandits
- Safe Exploration in Finite Markov Decision Processes with Gaussian Processes
- Online Regret Bounds for Undiscounted Continuous Reinforcement Learning
- Model-based Reinforcement Learning and the Eluder Dimension
- Thompson Sampling for Linear-Quadratic Control Problems
- Streaming kernel regression with provably adaptive mean, variance, and regularization