On the Benefits of Leveraging Structural Information in Planning Over the Learned Model
This work addresses sample efficiency for RL practitioners, but it is incremental as it builds on existing model-based RL by incorporating structural assumptions.
The paper tackles the high sample complexity in model-based reinforcement learning by leveraging known structural information about the system, showing significant reductions in sample requirements through theoretical analysis and examples like queuing systems and gridworlds.
Model-based Reinforcement Learning (RL) integrates learning and planning and has received increasing attention in recent years. However, learning the model can incur a significant cost (in terms of sample complexity), due to the need to obtain a sufficient number of samples for each state-action pair. In this paper, we investigate the benefits of leveraging structural information about the system in terms of reducing sample complexity. Specifically, we consider the setting where the transition probability matrix is a known function of a number of structural parameters, whose values are initially unknown. We then consider the problem of estimating those parameters based on the interactions with the environment. We characterize the difference between the Q estimates and the optimal Q value as a function of the number of samples. Our analysis shows that there can be a significant saving in sample complexity by leveraging structural information about the model. We illustrate the findings by considering several problems including controlling a queuing system with heterogeneous servers, and seeking an optimal path in a stochastic windy gridworld.