Fast exploration and learning of latent graphs with aliased observations
This addresses the challenge of efficient graph learning in partially observable environments, such as robotics or navigation, with incremental improvements over existing methods.
The paper tackles the problem of recovering a latent graph from aliased observations where multiple nodes share the same observation, using an agent to explore and learn transition probabilities efficiently. The result is an algorithm that is exponentially faster than naive exploration in aliased scenarios while remaining competitive in unaliased cases.
We consider the problem of recovering a latent graph where the observations at each node are \emph{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.