Markov Decision Processes (MDPs) are frameworks used to model decision-making in situations where outcomes are partly random and partly under the control of a decision maker. While small MDPs are inherently interpretable for people, MDPs with thousands of states are difficult to understand by humans. The K-MDP problem is the problem of finding the best MDP with, at most, K states by leveraging state abstraction approaches to aggregate states into sub-groups. The aim of this project is to measure and improve the interpretability of K-MDP approaches using state-of-the-art XAI approaches. We will instantiate and evaluate our approaches on a range of computational sustainability case studies from the domain of conservation of biodiversity, natural resource management and behavioural ecology.