Skip to Main content Skip to Navigation
Conference papers

Solving $K$-MDPs

Abstract : Markov Decision Processes (MDPs) are employed to model sequential decision-making problems under uncertainty. Traditionally, algorithms to solve MDPs have focused on solving large state or action spaces. With increasing applications of MDPs to human-operated domains such as conservation of biodiversity and health, developing easy-to-interpret solutions is of paramount importance to increase uptake of MDP policies. Here, we define the problem of solving K-MDPs, i.e., given an original MDP and a constraint on the number of states (K), generate a reduced state space MDP that minimizes the difference between the original optimal MDP value function and the reduced optimal K-MDP value function. Building on existing non-transitive and transitive approximate state abstraction functions, we propose a family of three algorithms based on binary search with sub-optimality bounded polynomially in a precision parameter: ϕQ*εK-MDP-ILP, ϕQ*dK-MDP and ϕa*dK-MDP. We compare these algorithms to a greedy algorithm (ϕQ*ε Greedy K-MDP) and clustering approach (k-means++ K-MDP). On randomly generated MDPs and two computational sustainability MDPs, ϕa*dK-MDP outperformed all algorithms when it could find a feasible solution. While numerous state abstraction problems have been proposed in the literature, this is the first time that the general problem of solving K-MDPs is suggested. We hope that our work will generate future research aiming at increasing the interpretability of MDP policies in human-operated domains.
Document type :
Conference papers
Complete list of metadata
Contributor : Olivier Buffet Connect in order to contact the contributor
Submitted on : Thursday, December 17, 2020 - 10:07:09 PM
Last modification on : Wednesday, November 3, 2021 - 7:57:20 AM


  • HAL Id : hal-03080154, version 1



Jonathan Ferrer-Mestres, Thomas Dietterich, Olivier Buffet, Iadine Chadès. Solving $K$-MDPs. ICAPS 2020 - International Conference on Automated Planning and Scheduling, Oct 2020, Nancy (virtuel), France. ⟨hal-03080154⟩



Record views