# On the Benefits of Leveraging Structural Information in Planning Over the Learned Model

arXiv: https://arxiv.org/abs/2303.08856 · HTML: https://mlsanity.com/paper/2303.08856/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 28 references that are in the map.
- First posted on arXiv 15 Mar 2023.

## Builds on (most cited first, 9 of 9)

- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Hidden Parameter Markov Decision Processes: A Semiparametric Regression Approach for Discovering Latent Task Parametrizations](https://mlsanity.com/paper/1308.3513/) (2013)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach](https://mlsanity.com/paper/2202.00063/) (2022)
- [Multi-step Reinforcement Learning: A Unifying Algorithm](https://mlsanity.com/paper/1703.01327/) (2017)
- [Robust and Efficient Transfer Learning with Hidden-Parameter Markov Decision Processes](https://mlsanity.com/paper/1706.06544/) (2017)
- [Generalized Hidden Parameter MDPs Transferable Model-based RL in a Handful of Trials](https://mlsanity.com/paper/2002.03072/) (2020)
- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)

## Abstract (arXiv)

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.