Regret Bounds for Learning State Representations in Reinforcement Learning
Ronald Ortner, Matteo Pirotta, Alessandro Lazaric, Ronan Fruit, Odalric-Ambrym Maillard
Abstract
We consider the problem of online reinforcement learning when several state representations (mapping histories to a discrete state space) are available to the learning agent. At least one of these representations is assumed to induce a Markov decision process (MDP), and the performance of the agent is measured in terms of cumulative regret against the optimal policy giving the highest average reward in this MDP representation. We propose an algorithm (UCB-MS) with O(sqrt(T)) regret in any communicating Markov decision process. The regret bound shows that UCB-MS automatically adapts to the Markov model. This improves over the currently known best results in the literature that gave regret bounds of order O(T^(2/3)).
BibTeX
@inproceedings{NEURIPS2019_9b8b50fb,
author = {Ortner, Ronald and Pirotta, Matteo and Lazaric, Alessandro and Fruit, Ronan and Maillard, Odalric-Ambrym},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Regret Bounds for Learning State Representations in Reinforcement Learning},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/9b8b50fb590c590ffbf1295ce92258dc-Paper.pdf},
volume = {32},
year = {2019}
}