# An Analysis of Model-Based Reinforcement Learning From Abstracted Observations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 47 references that are in the map.
- First posted on arXiv 30 Aug 2022.

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

- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Near Optimal Behavior via Approximate State Abstraction](https://mlsanity.com/paper/1701.04113/) (2017)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Plannable Approximations to MDP Homomorphisms: Equivariance under Actions](https://mlsanity.com/paper/2002.11963/) (2020)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Learning Markov State Abstractions for Deep Reinforcement Learning](https://mlsanity.com/paper/2106.04379/) (2021)
- [Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs](https://mlsanity.com/paper/1803.01626/) (2018)
- [Variational Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1905.05857/) (2019)
- [Tightening Exploration in Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2004.09656/) (2020)
- [The Sample-Complexity of General Reinforcement Learning](https://mlsanity.com/paper/1308.4828/) (2013)
- [Reinforcement Learning in Rich-Observation MDPs using Spectral Methods](https://mlsanity.com/paper/1611.03907/) (2016)
- [Online Abstraction with MDP Homomorphisms for Deep Learning](https://mlsanity.com/paper/1811.12929/) (2018)
- [Sampling-Based Robust Control of Autonomous Systems with Non-Gaussian Noise](https://mlsanity.com/paper/2110.12662/) (2021)
- [Adaptive Discretization in Online Reinforcement Learning](https://mlsanity.com/paper/2110.15843/) (2021)
- [Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes](https://mlsanity.com/paper/1302.1533/) (2013)
- [Selecting Near-Optimal Approximate State Representations in Reinforcement Learning](https://mlsanity.com/paper/1405.2652/) (2014)
- [Optimal Regret Bounds for Selecting the State Representation in Reinforcement Learning](https://mlsanity.com/paper/1302.2553/) (2013)
- [Approximate Exploration through State Abstraction](https://mlsanity.com/paper/1808.09819/) (2018)

## Built on by (most cited first, 2 of 2)

- [On the Sample Efficiency of Abstractions and Potential-Based Reward Shaping in Reinforcement Learning](https://mlsanity.com/paper/2404.07826/) (2024)
- [Goal-oriented inference of environment from redundant observations](https://mlsanity.com/paper/2305.04432/) (2023)

## Abstract (arXiv)

Many methods for Model-based Reinforcement learning (MBRL) in Markov decision processes (MDPs) provide guarantees for both the accuracy of the model they can deliver and the learning efficiency. At the same time, state abstraction techniques allow for a reduction of the size of an MDP while maintaining a bounded loss with respect to the original problem. Therefore, it may come as a surprise that no such guarantees are available when combining both techniques, i.e., where MBRL merely observes abstract states. Our theoretical analysis shows that abstraction can introduce a dependence between samples collected online (e.g., in the real world). That means that, without taking this dependence into account, results for MBRL do not directly extend to this setting. Our result shows that we can use concentration inequalities for martingales to overcome this problem. This result makes it possible to extend the guarantees of existing MBRL algorithms to the setting with abstraction. We illustrate this by combining R-MAX, a prototypical MBRL algorithm, with abstraction, thus producing the first performance guarantees for model-based 'RL from Abstracted Observations': model-based reinforcement learning with an abstract model.