Learning Coarser Markov State Abstractions

State abstractions in reinforcement learning create compact representations, and increase sample-efficiency, by keeping information in observations that is relevant for decision-making while discarding other regularities. Recently introduced Markov state abstractions (MSAs) define reward-free sufficient conditions under which the learned representation is Markov. However, current implementations of the MSA objectives satisfy a stronger (kinematic inseparability) condition, which results in over-refined abstractions that preserve all transition regularities in the observation. We show for the first time how to align the training objective with the original theoretical MSA conditions and thus build coarser abstractions. This objective drives the representation to satisfy sufficient Markov conditions, but does not, by itself, guarantee minimality. We therefore provide an additional heuristic to push the representation towards minimality. Our experiments in pixel-based domains show that the learned abstractions recover the underlying complexity of the problem, which improves downstream performance.