# Fast exploration and learning of latent graphs with aliased observations

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

## Key facts

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

## Builds on (most cited first, 30 of 34)

- [Mastering Atari with Discrete World Models](https://mlsanity.com/paper/2010.02193/) (2020)
- [Recurrent World Models Facilitate Policy Evolution](https://mlsanity.com/paper/1809.01999/) (2018)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Learning to Explore using Active Neural SLAM](https://mlsanity.com/paper/2004.05155/) (2020)
- [First return, then explore](https://mlsanity.com/paper/2004.12919/) (2020)
- [Human-level performance in first-person multiplayer games with population-based deep reinforcement learning](https://mlsanity.com/paper/1807.01281/) (2018)
- [Stochastic Latent Actor-Critic: Deep Reinforcement Learning with a Latent Variable Model](https://mlsanity.com/paper/1907.00953/) (2019)
- [Cognitive Mapping and Planning for Visual Navigation](https://mlsanity.com/paper/1702.03920/) (2017)
- [Semi-parametric Topological Memory for Navigation](https://mlsanity.com/paper/1803.00653/) (2018)
- [Deep Variational Reinforcement Learning for POMDPs](https://mlsanity.com/paper/1806.02426/) (2018)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [A Laplacian Framework for Option Discovery in Reinforcement Learning](https://mlsanity.com/paper/1703.00956/) (2017)
- [Model-Based Active Exploration](https://mlsanity.com/paper/1810.12162/) (2018)
- [Neural Map: Structured Memory for Deep Reinforcement Learning](https://mlsanity.com/paper/1702.08360/) (2017)
- [Eigenoption Discovery through the Deep Successor Representation](https://mlsanity.com/paper/1710.11089/) (2017)
- [DeepMind Lab](https://mlsanity.com/paper/1612.03801/) (2016)
- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [Shaping Belief States with Generative Environment Models for RL](https://mlsanity.com/paper/1906.09237/) (2019)
- [QMDP-Net: Deep Learning for Planning under Partial Observability](https://mlsanity.com/paper/1703.06692/) (2017)
- [Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach](https://mlsanity.com/paper/2202.00063/) (2022)
- [Variational Recurrent Models for Solving Partially Observable Control Tasks](https://mlsanity.com/paper/1912.10703/) (2019)
- [Guaranteed Discovery of Control-Endogenous Latent States with Multi-Step Inverse Models](https://mlsanity.com/paper/2207.08229/) (2022)
- [Mapping State Space using Landmarks for Universal Goal Reaching](https://mlsanity.com/paper/1908.05451/) (2019)
- [Evaluating Long-Term Memory in 3D Mazes](https://mlsanity.com/paper/2210.13383/) (2022)
- [Solving POMDPs by Searching the Space of Finite Policies](https://mlsanity.com/paper/1301.6720/) (2013)
- [Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes](https://mlsanity.com/paper/1302.1525/) (2013)
- [Rapid Task-Solving in Novel Environments](https://mlsanity.com/paper/2006.03662/) (2020)
- [Representing higher-order dependencies in networks](https://mlsanity.com/paper/1508.03113/) (2015)
- [Benefits of over-parameterization with EM](https://mlsanity.com/paper/1810.11344/) (2018)

## Abstract (arXiv)

We consider the problem of recovering a latent graph where the observations at each node are aliased, and transitions are stochastic. Observations are gathered by an agent traversing the graph. Aliasing means that multiple nodes emit the same observation, so the agent can not know in which node it is located. The agent needs to uncover the hidden topology as accurately as possible and in as few steps as possible. This is equivalent to efficient recovery of the transition probabilities of a partially observable Markov decision process (POMDP) in which the observation probabilities are known. An algorithm for efficiently exploring (and ultimately recovering) the latent graph is provided. Our approach is exponentially faster than naive exploration in a variety of challenging topologies with aliased observations while remaining competitive with existing baselines in the unaliased regime.