@inproceedings{0bacacaac6604f9c9ab9c7bdb60b42de,
title = "Extreme state aggregation beyond MDPs",
abstract = "We consider a Reinforcement Learning setup without any (esp. MDP) assumptions on the environment. State aggregation and more generally feature reinforcement learning is concerned with mapping histories/raw-states to reduced/aggregated states. The idea behind both is that the resulting reduced process (approximately) forms a small stationary finite-state MDP, which can then be efficiently solved or learnt. We considerably generalize existing aggregation results by showing that even if the reduced process is not an MDP, the (q-)value functions and (optimal) policies of an associated MDP with same state-space size solve the original problem, as long as the solution can approximately be represented as a function of the reduced states. This implies an upper bound on the required state space size that holds uniformly for all RL problems. It may also explain why RL algorithms designed for MDPs sometimes perform well beyond MDPs.",
keywords = "Non-MDP, Reinforcement learning, State aggregation",
author = "Marcus Hutter",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.; 25th International Conference on Algorithmic Learning Theory, ALT 2014 ; Conference date: 08-10-2014 Through 10-10-2014",
year = "2014",
doi = "10.1007/978-3-319-11662-4_14",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "185--199",
editor = "Peter Auer and Alexander Clark and Thomas Zeugmann and Sandra Zilles",
booktitle = "Algorithmic Learning Theory - 25th International Conference, ALT 2014, Proceedings",
address = "Germany",
}