Beyond markov decision processes: How to leverage structure to build efficient reinforcement learning algorithms

A Markov Decision Process (MDP) describes a general framework for modelling decision-making in an uncertain environment. Over the years, researchers have mainly focused on developing Reinforcement Learning (RL) algorithms to learn how to behave optimally in unknown environments without making explicit assumptions about the existence of underlying structures in the MDP. This general approach has been instrumental to RL's widespread success across various domains. However, when additional structure is present and exploitable, enabling algorithms to leverage it might lead to significant efficiency improvement. This work investigates the benefits of designing RL algorithms that can efficiently leverage these structures. Specifically, this work focuses on two distinct types of known latent structures. First, we consider MDPs that exhibit a hierarchical structure; that is, tasks described by such MDPs can be decomposed into a sequence of sub-tasks. In this context, we provide a lower bound on the sample complexity of hierarchical RL algorithms, which allows us to quantify the potential benefit of hierarchical approaches. We also offer a framework for building hierarchical algorithms that leverage a known hierarchical decomposition. The validity of that framework is supported by theoretical guarantees of its efficiency and empirical evidence that it outperforms its monolithic counterpart whenever a hierarchical structure is present. Second, we consider MDPs that exhibit a graphical structure. The algorithm has access to a graph that encodes the conditional independence between state variables, and the unknown dynamics can be inferred only by local components of the graph. In this context, we provide a posterior sampling-based algorithm that theoretically and empirically outperforms RL algorithms that do not leverage this structural property. Finally, we provide empirical evidence that this latent graphical structure is present in optimising wind farms' yields and demonstrate the efficiency of our algorithm on that particular task.