Optimal Decision Tree Policies for Markov Decision Processes

Optimal Decision Tree Policies for Markov Decision Processes

Vos, D.A. (TU Delft Cyber Security)
Verwer, S.E. (TU Delft Cyber Security)

Elkind, Edith (editor)

2023

Interpretability of reinforcement learning policies is essential for many real-world tasks but learning such interpretable policies is a hard problem. Particularly, rule-based policies such as decision trees and rules lists are difficult to optimize due to their non-differentiability. While existing techniques can learn verifiable decision tree policies, there is no guarantee that the learners generate a policy that performs optimally. In this work, we study the optimization of size-limited decision trees for Markov Decision Processes (MPDs) and propose OMDTs: Optimal MDP Decision Trees. Given a user-defined size limit and MDP formulation, OMDT directly maximizes the expected discounted return for the decision tree using Mixed-Integer Linear Programming. By training optimal tree policies for different MDPs we empirically study the optimality gap for existing imitation learning techniques and find that they perform sub-optimally. We show that this is due to an inherent shortcoming of imitation learning, namely that complex policies cannot be represented using size-limited trees. In such cases, it is better to directly optimize the tree for expected return. While there is generally a trade-off between the performance and interpretability of machine learning models, we find that on small MDPs, depth 3 OMDTs often perform close to optimally.

http://resolver.tudelft.nl/uuid:1b398fb2-d8b1-423e-bddd-08e50867a59b

International Joint Conferences on Artificial Intelligence (IJCAI)

9781956792034

Proceedings of the 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023

32nd International Joint Conference on Artificial Intelligence, IJCAI 2023, 2023-08-19 → 2023-08-25, Macao, China

IJCAI International Joint Conference on Artificial Intelligence, 1045-0823, 2023-August

Institutional Repository

conference paper

© 2023 D.A. Vos, S.E. Verwer