Optimal Decision Tree Policies for Markov Decision Processes

Daniël Vos, Sicco VerwerIJCAI 2023 · DOI

TL;DR

This paper introduces OMDT, a novel Mixed-Integer Linear Programming (MILP) formulation for directly optimizing size-limited decision tree policies in Markov Decision Processes (MDPs). By formulating the problem as an MILP, OMDT guarantees optimality for the learned tree policy under a given size constraint, addressing a key limitation of existing imitation learning approaches.

What Problem Does This Paper Address?

Reinforcement learning (RL) agents often learn complex, uninterpretable policies, typically neural networks, which hinders their adoption in high-stakes decision-making scenarios. While decision trees offer interpretability, optimizing them for RL tasks is challenging due to their non-differentiable nature. Existing methods for learning interpretable decision tree policies in RL often rely on imitation learning (e.g., VIPER), which learns from a teacher policy. However, these methods don't guarantee optimality and can be inefficient, as they might waste the limited capacity of a small tree on parts of the state space that the student policy will never reach. This paper aims to bridge the gap between optimal decision tree learning and RL by developing a method that directly optimizes size-limited decision tree policies for MDPs, guaranteeing optimality under the size constraint.

Methods

The core contribution is the OMDT (Optimal MDP Decision Trees) formulation. This is a Mixed-Integer Linear Programming (MILP) model that combines two key components:

  1. MDP Optimization: It leverages the dual linear program formulation for solving MDPs. This formulation allows reasoning about policies explicitly, which is more efficient than primal formulations.
  2. Decision Tree Constraints: It introduces a set of constraints that restrict the feasible policies to be size-limited decision trees. This involves modeling decision nodes with binary threshold variables and defining how observations traverse the tree based on these thresholds. The formulation avoids "big-M" constraints for path traversal, leading to stronger relaxations and better bounds.

The MILP solver then directly maximizes the expected discounted return of the MDP subject to the decision tree policy constraints and the size limit.

Datasets

The paper evaluates OMDT on 13 environments derived from well-known MDP benchmarks. These include:

  • 3d_navigation
  • blackjack
  • frozenlake (4x4, 8x8, 12x12)
  • inventory management
  • sysadmin (1, 2, tree)
  • tictactoe_vs_random
  • tiger_vs_antelope
  • traffic_intersection
  • xor

These environments vary in state and action space sizes, and some are designed to be challenging for greedy decision tree learning algorithms (e.g., XOR).

Key Insights and Ideas

  • Direct Optimization vs. Imitation Learning: The paper strongly argues that for interpretable policies (small decision trees), direct optimization (OMDT) is superior to imitation learning (VIPER). Imitation learning can be inefficient because it tries to mimic a complex teacher policy, potentially wasting the limited capacity of a small student tree on unreachable states.
  • Optimality Guarantees: OMDT's MILP formulation provides a crucial advantage: it can prove the optimality of the learned decision tree policy under the given size constraint. This is a significant step beyond existing methods that offer no such guarantees.
  • Performance-Interpretability Trade-off: For small MDPs and shallow trees (depth 3), the paper finds that there is often no performance trade-off. OMDT policies achieve near-optimal performance while remaining interpretable, challenging the common assumption that interpretability comes at the cost of performance.
  • MILP Efficiency: The formulation's clever use of the dual LP and avoidance of "big-M" constraints for path traversal contributes to its effectiveness in solving these complex optimization problems.

Key Results

  • Performance: On 8 out of 13 environments, depth 3 OMDTs achieved performance close to optimal. In the Frozenlake 12x12 environment, OMDT significantly outperformed VIPER (66% success vs. 11% success) by directly optimizing the policy.
  • Optimality Proofs: OMDT successfully proved optimality for size-limited trees in 7 out of 13 environments within a 2-hour runtime limit.
  • Tree Size: OMDT produces significantly smaller trees than methods like dtcontrol (which aims to replicate the unrestricted policy). For example, on 3d_navigation, OMDT produced a 7-node tree while dtcontrol produced a 68-node tree, with comparable performance.
  • Runtime: While OMDT can take longer to prove optimality than VIPER runs for a fixed time, it often finds good policies much faster and eventually surpasses VIPER's performance in most environments when given sufficient time.

Limitations and Future Work

  • MDP Specification: OMDT requires a full specification of the Markov Decision Process (states, actions, transitions, rewards). Future work could explore incorporating factored MDPs into the formulation to scale to larger state spaces.
  • Simulation-Based Learning: Unlike imitation learning methods that can learn from simulation, OMDT needs a complete model. Future work could focus on bridging this gap by developing methods that optimize interpretable decision trees using only simulation access.
  • Runtime for Optimality: Proving optimality for deeper trees can be computationally expensive, and OMDT timed out on several environments within the 2-hour limit. Further research into more efficient MILP solvers or alternative optimization techniques could address this.

Summary updated

BibTeX
@inproceedings{vos2023optimal,
  author = {Daniël Vos and Sicco Verwer},
  title = {{Optimal Decision Tree Policies for Markov Decision Processes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/606},
}
Figure