# Planning to the Information Horizon of BAMDPs via Epistemic State Abstraction

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 105 references that are in the map.
- First posted on arXiv 30 Oct 2022.

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

- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learning](https://mlsanity.com/paper/1910.08348/) (2019)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [The Uncertainty Bellman Equation and Exploration](https://mlsanity.com/paper/1709.05380/) (2017)
- [Meta-learning of Sequential Strategies](https://mlsanity.com/paper/1905.03030/) (2019)
- [Near Optimal Behavior via Approximate State Abstraction](https://mlsanity.com/paper/1701.04113/) (2017)
- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Increasing the Action Gap: New Operators for Reinforcement Learning](https://mlsanity.com/paper/1512.04860/) (2015)
- [Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States](https://mlsanity.com/paper/2102.05261/) (2021)
- [Meta-trained agents implement Bayes-optimal agents](https://mlsanity.com/paper/2010.11223/) (2020)
- [On the Complexity of Solving Markov Decision Problems](https://mlsanity.com/paper/1302.4971/) (2013)
- [Exploration in Approximate Hyper-State Space for Meta Reinforcement Learning](https://mlsanity.com/paper/2010.01062/) (2020)
- [A Theory of Abstraction in Reinforcement Learning](https://mlsanity.com/paper/2203.00397/) (2022)
- [Provably Efficient Reinforcement Learning with Aggregated States](https://mlsanity.com/paper/1912.06366/) (2019)
- [An Information-Theoretic Perspective on Credit Assignment in Reinforcement Learning](https://mlsanity.com/paper/2103.06224/) (2021)
- [Bayesian Policy Optimization for Model Uncertainty](https://mlsanity.com/paper/1810.01014/) (2018)
- [Mitigating Planner Overfitting in Model-Based Reinforcement Learning](https://mlsanity.com/paper/1812.01129/) (2018)
- [Randomized Value Functions via Posterior State-Abstraction Sampling](https://mlsanity.com/paper/2010.02383/) (2020)
- [Bad-Policy Density: A Measure of Reinforcement Learning Hardness](https://mlsanity.com/paper/2110.03424/) (2021)

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

- [Toward Efficient Exploration by Large Language Model Agents](https://mlsanity.com/paper/2504.20997/) (2025)
- [Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM Reasoning](https://mlsanity.com/paper/2505.20561/) (2025)
- [Satisficing Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/2407.12185/) (2024)
- [Cognitive Models and AI Algorithms Provide Templates for Designing Language Agents](https://mlsanity.com/paper/2602.22523/) (2026)

## Abstract (arXiv)

The Bayes-Adaptive Markov Decision Process (BAMDP) formalism pursues the Bayes-optimal solution to the exploration-exploitation trade-off in reinforcement learning. As the computation of exact solutions to Bayesian reinforcement-learning problems is intractable, much of the literature has focused on developing suitable approximation algorithms. In this work, before diving into algorithm design, we first define, under mild structural assumptions, a complexity measure for BAMDP planning. As efficient exploration in BAMDPs hinges upon the judicious acquisition of information, our complexity measure highlights the worst-case difficulty of gathering information and exhausting epistemic uncertainty. To illustrate its significance, we establish a computationally-intractable, exact planning algorithm that takes advantage of this measure to show more efficient planning. We then conclude by introducing a specific form of state abstraction with the potential to reduce BAMDP complexity and gives rise to a computationally-tractable, approximate planning algorithm.