Learning the Minimum Action Distance

This paper presents a state representation framework for Markov decision processes (MDPs) that can be learned solely from state trajectories, requiring neither reward signals nor the actions executed by the agent. We propose learning the $\textit{minimum action distance}$ (MAD), defined as the minimum number of actions required to transition between states, as a fundamental metric that captures the underlying structure of an environment. The MAD naturally enables critical downstream tasks such as goal-conditioned reinforcement learning and reward shaping by providing a dense, geometrically meaningful measure of progress. Our self-supervised learning approach constructs an embedding space where the distances between embedded state pairs correspond to their MAD, accommodating both symmetric and asymmetric approximations. We evaluate the framework on a comprehensive suite of environments with known MAD values, encompassing both deterministic and stochastic transition dynamics, discrete and continuous state spaces, and environments with noisy observations. Empirical results show that the proposed approach learns MAD representations more efficiently than existing methods, produces more accurate estimates of the true MAD, and improves performance on downstream goal-reaching tasks.

Intelligent systems need to understand the structure of the world around them. For example, they may need to estimate how difficult it is to get from one situation to another, whether navigating a maze, controlling a robot, or planning a sequence of actions. However, learning this structure is often challenging because it requires detailed information about actions, goals, or rewards. In this work, we introduce a method that learns the structure of an environment simply by observing sequences of states. Instead of relying on additional information, our approach learns how “far apart” different situations are in terms of the minimum effort required to move between them. We tested the method in a wide variety of environments, including settings with randomness, noisy observations, and both simple and complex forms of movement. Across all of these scenarios, the method consistently learned accurate representations of the underlying structure and outperformed existing approaches. By helping systems better understand how different situations are connected, this work can support a broad range of future applications, including planning, decision making, and autonomous systems. More generally, it provides a way to learn meaningful structure from observations alone, without requiring extensive human-designed guidance.