Learning The Minimum Action Distance

[Submitted on 10 Jun 2025 (v1), last revised 7 Jul 2026 (this version, v4)]

View PDF HTML (experimental)

Abstract: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 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. 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 dynamics, as well as discrete and continuous state spaces, and environments with noisy observations. Empirical results demonstrate that the proposed approach not only efficiently learns accurate MAD representations across these diverse settings but also significantly outperforms existing state representation methods in terms of representation quality.

Submission history

From: Lorenzo Steccanella [view email]
[v1] Tue, 10 Jun 2025 22:27:11 UTC (2,056 KB)
[v2] Mon, 6 Oct 2025 18:53:43 UTC (13,512 KB)
[v3] Tue, 24 Mar 2026 09:31:25 UTC (17,605 KB)
[v4] Tue, 7 Jul 2026 00:07:34 UTC (9,978 KB)