Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning
This addresses fundamental efficiency and theoretical issues in HRL for researchers and practitioners, though it appears incremental as it builds on existing abstraction concepts.
The paper tackles the limited expressive power and lack of formal guarantees in Hierarchical Reinforcement Learning (HRL) by introducing Realizable Abstractions, which enable near-optimal policies for low-level MDPs with polynomial sample convergence and robustness to inaccuracies.
The main focus of Hierarchical Reinforcement Learning (HRL) is studying how large Markov Decision Processes (MDPs) can be more efficiently solved when addressed in a modular way, by combining partial solutions computed for smaller subtasks. Despite their very intuitive role for learning, most notions of MDP abstractions proposed in the HRL literature have limited expressive power or do not possess formal efficiency guarantees. This work addresses these fundamental issues by defining Realizable Abstractions, a new relation between generic low-level MDPs and their associated high-level decision processes. The notion we propose avoids non-Markovianity issues and has desirable near-optimality guarantees. Indeed, we show that any abstract policy for Realizable Abstractions can be translated into near-optimal policies for the low-level MDP, through a suitable composition of options. As demonstrated in the paper, these options can be expressed as solutions of specific constrained MDPs. Based on these findings, we propose RARL, a new HRL algorithm that returns compositional and near-optimal low-level policies, taking advantage of the Realizable Abstraction given in the input. We show that RARL is Probably Approximately Correct, it converges in a polynomial number of samples, and it is robust to inaccuracies in the abstraction.