TY - JOUR

T1 - Graph learning-based generation of abstractions for reinforcement learning

AU - Xue, Yuan

AU - Kudenko, Daniel

AU - Khosla, Megha

N1 - Funding Information: This work was partially funded by the Federal Ministry of Education and Research (BMBF), Germany, under the project LeibnizKILabor (Grant No. 01DD20003). Open Access funding enabled and organized by Projekt DEAL

PY - 2023

Y1 - 2023

N2 - The application of reinforcement learning (RL) algorithms is often hindered by the combinatorial explosion of the state space. Previous works have leveraged abstractions which condense large state spaces to find tractable solutions. However, they assumed that the abstractions are provided by a domain expert. In this work, we propose a new approach to automatically construct abstract Markov decision processes (AMDPs) for potential-based reward shaping to improve the sample efficiency of RL algorithms. Our approach to constructing abstract states is inspired by graph representation learning methods, it effectively encodes the topological and reward structure of the ground-level MDP. We perform large-scale quantitative experiments on a range of navigation and gathering tasks under both stationary and stochastic settings. Our approach shows improvements of up to 8.5 times in sample efficiency and up to 3 times in run time over the baseline approach. Besides, with our qualitative analyses of the generated AMDPs, we are able to visually demonstrate the capability of our approach to preserve the topological and reward structure of the ground-level MDP.

AB - The application of reinforcement learning (RL) algorithms is often hindered by the combinatorial explosion of the state space. Previous works have leveraged abstractions which condense large state spaces to find tractable solutions. However, they assumed that the abstractions are provided by a domain expert. In this work, we propose a new approach to automatically construct abstract Markov decision processes (AMDPs) for potential-based reward shaping to improve the sample efficiency of RL algorithms. Our approach to constructing abstract states is inspired by graph representation learning methods, it effectively encodes the topological and reward structure of the ground-level MDP. We perform large-scale quantitative experiments on a range of navigation and gathering tasks under both stationary and stochastic settings. Our approach shows improvements of up to 8.5 times in sample efficiency and up to 3 times in run time over the baseline approach. Besides, with our qualitative analyses of the generated AMDPs, we are able to visually demonstrate the capability of our approach to preserve the topological and reward structure of the ground-level MDP.

KW - Abstract MDP

KW - Graph representations

KW - Reinforcement learning

KW - State representations

UR - http://www.scopus.com/inward/record.url?scp=85147750411&partnerID=8YFLogxK

U2 - 10.1007/s00521-023-08211-x

DO - 10.1007/s00521-023-08211-x

M3 - Article

AN - SCOPUS:85147750411

VL - 2023

JO - Neural Computing and Applications

JF - Neural Computing and Applications

SN - 0941-0643

ER -