Exploration in relational worlds

Abstract. One of the key problems in model-based reinforcement learn-ing is balancing exploration and exploitation. Another is learning and acting in large relational domains, in which there is a varying number of objects and relations between them. We provide one of the first so-lutions to exploring large relational Markov decision processes by devel-oping relational extensions of the concepts of the Explicit Explore or Exploit (E3) algorithm. A key insight is that the inherent generalization of learnt knowledge in the relational representation has profound impli-cations also on the exploration strategy: what in a propositional setting would be considered a novel situation and worth exploration may in the relational setting be an instance of a well-known context in which exploitation is promising. Our experimental evaluation shows the effec-tiveness and benefit of relational exploration over several propositional benchmark approaches on noisy 3D simulated robot manipulation prob-lems.